BZOJ-1782: [Usaco2010 Feb]slowdown 慢慢游

Description

给你一棵树，和节点时间顺序。求每个节点在自己的时刻有多少个点已经出现在点与根之间的路径上。n<=100000

看到到根节点的链直接想到dfs入栈出栈序。然后树状数组维护一下模拟没得说。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,p[101000],in[101000],out[101000],tot;
int f[201000];
int head[101000],to[201000],nxt[201000],cnt;
void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x,int pre)
{
    in[x]=++tot;
    for(int i=head[x];i;i=nxt[i])
        if(to[i]!=pre)
            dfs(to[i],x);
    out[x]=++tot;
}
int query(int x)
{
    int re=0;
    while(x>0) re+=f[x],x-=-x&x;
    return re;
}
void fix(int x,int w)
{
    while(x<=tot) f[x]+=w,x+=-x&x;
}
int main()
{
    scanf("%d",&n); int i,x,y;
    for(i=1;i!=n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    for(i=1;i<=n;++i) scanf("%d",p+i);
    dfs(1,0);
    for(i=1;i<=n;i++)
    {
        printf("%d\n",query(in[p[i]]));
        fix(in[p[i]],1);
        fix(out[p[i]],-1);
    }
    return 0;
}