自动搬运

查看原文

来自洛谷，原作者为

	insprition **

搬运于2025-08-24 21:44:05，当前版本为作者最后更新于2017-05-12 21:22:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

线段树 dfs序

数据结构的应用

“数据结构 是先有需求 再有应用” by mzx dalao

那么按照这个思路

先看看针对这道题 有什么需求

再考虑用什么数据结构去解决

以及怎么用该数据结构

这是一个树上的题

某个牛进了牧场

只会影响到他子树的答案

因为只有他的 子树 回牧场时

才要经过他 得slowing down对吧

这时 要对他的 子树的答案全部 区间+1

这是 对dfs序的需求

需要 dfs序 将树转换成区间

区间修改 单点查询 又是对 线段树 的需求

需要 线段树 的高效维护

如有dalao有更高效的方法请博客留言

我目前只学了线段树这个家伙啦

具体应用

dfs序

void dfs(int u){
    dfn[u]=++cnt;//dfn[]为树转换为dfs序中的下标
    size[u]=1;//u为根的子树大小
    int v;
    for(int i=head[u];i;i=next[i]){
        v=to[i];
        if(dfn[v])continue;
        dfs(v);
        size[u]+=size[v];
    }
}

这样一棵子树 就对应了 dfn[]数组 的一段区间 以点k为根的 区间

左端点 是 dfn[k],

右端点 是 dfn[k] + size [k] - 1 。

线段树

//main() 函数中的代码
for(int k,i=1;i<=n;i++){
      k=read();
      //单点查询
      printf("%d\n",query(dfn[k],root));
      //区间修改
      update(dfn[k],dfn[k]+size[k]-1,root);
}
//其他函数
 void pushdown(int rt){//懒标记下传
    if(!add[rt])return;
    add[rt<<1]+=add[rt];
    add[rt<<1|1]+=add[rt];
    add[rt]=0;
}
void update(int x,int y,int l,int r,int rt){
    if(x<=l&&r<=y){
        add[rt]++;//区间修改时 针对本题 懒标记+1 
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid)update(x,y,lson);
    if(mid<y)update(x,y,rson);
}
int query(int k,int l,int r,int rt){
    //单点查询 所以线段树只用 懒标记add[]数组 即可
    if(l==r)return add[rt];
    pushdown(rt);
    int mid=(l+r)>>1;
    if(k<=mid)return query(k,lson);
    return query(k,rson);
}

这样就 滋瓷 了本题的修改与查询操作 完

总代码

#include<bits/stdc++.h>
using namespace std;
#define N 100015
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int n,cnt;
int head[N],next[N<<1],to[N<<1];
int dfn[N],size[N];
int add[N<<2];
int read(){
    int ans=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);ch=getchar())
        ans=(ans<<3)+(ans<<1)+ch-'0';
    return ans;
}
void ad(int from,int too){
    next[++cnt]=head[from];
    to[cnt]=too;
    head[from]=cnt;
}
void dfs(int u){
    dfn[u]=++cnt;//dfn[]为树转换为dfs序中的下标
    size[u]=1;//u为根的子树大小
    int v;
    for(int i=head[u];i;i=next[i]){
        v=to[i];
        if(dfn[v])continue;
        dfs(v);
        size[u]+=size[v];
    }
}
void pushdown(int rt){//懒标记下传
    if(!add[rt])return;
    add[rt<<1]+=add[rt];
    add[rt<<1|1]+=add[rt];
    add[rt]=0;
}
void update(int x,int y,int l,int r,int rt){
    if(x<=l&&r<=y){
        add[rt]++;//区间修改时 针对本题 懒标记+1 
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(x<=mid)update(x,y,lson);
    if(mid<y)update(x,y,rson);
}
int query(int k,int l,int r,int rt){
    //单点查询 所以线段树只用 懒标记add[]数组 即可
    if(l==r)return add[rt];
    pushdown(rt);
    int mid=(l+r)>>1;
    if(k<=mid)return query(k,lson);
    return query(k,rson);
}
int main(){
    n=read();
    for(int x,y,i=1;i<n;i++){
        x=read(),y=read();
        ad(x,y);
        ad(y,x);
    }
    cnt=0;
    dfs(1);
    for(int k,i=1;i<=n;i++){
        k=read();
        //单点查询
        printf("%d\n",query(dfn[k],root));
        //区间修改
        update(dfn[k],dfn[k]+size[k]-1,root);
    }
    return 0;
}