[JLOI2014]松鼠的新家（luogu）
Description
题目描述
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。
天哪，他居然真的住在”树“上。
松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，......，最后到an，去参观新家。
可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。
维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
输入格式
第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
输出格式
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
Solution
树链剖分区间加减（注意每次去另一个地方参观终点不用加一个糖果（=+1-1））
Code
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;
const int N=3e5+;
vector <int> link[N];
struct node
{
int l,r,lc,rc,tag,d;
}f[N*];
int rt,top[N],si[N],fa[N],tot,cnt,n,u,v,
dfn[N],dep[N],son[N],c[N],q[N],re[N];
void dfs1(int u,int fx)
{
dep[u]=dep[fx]+,fa[u]=fx,si[u]=;
int size=link[u].size();
for(int i=;i<size;i++)
{
int v=link[u][i];
if(v==fx) continue;
dfs1(v,u);
si[u]+=si[v];
if(!son[u] || si[son[u]]<si[v]) son[u]=v;
}
}
void dfs2(int u,int fx)
{
dfn[u]=++tot,re[tot]=u;
if(!son[u]) return ;
top[son[u]]=top[u],dfs2(son[u],u);
int size=link[u].size();
for(int i=;i<size;i++)
{
int v=link[u][i];
if(v==son[u] || v==fx) continue;
top[v]=v,dfs2(v,u);
}
}
void build(int l,int r,int &g)
{
g=++cnt,f[g].l=l,f[g].r=r;
f[g].tag=;
if(l==r)
{
f[g].d=re[l];
return;
}
int mid=(l+r)>>;
build(l,mid,f[g].lc);
build(mid+,r,f[g].rc);
}
void add(int g,int l,int r)
{
if(f[g].l==l && f[g].r==r)
{
f[g].tag++;
return;
}
int mid=(f[g].l+f[g].r)>>;
if(r<=mid) add(f[g].lc,l,r);
else if(l>mid) add(f[g].rc,l,r);
else add(f[g].lc,l,mid),add(f[g].rc,mid+,r);
}
void Add(int x,int y)
{
int px=top[x],py=top[y];
while(px!=py)
if(dep[px]>=dep[py])
{
add(rt,dfn[px],dfn[x]);
x=fa[px],px=top[x];
}
else
{
add(rt,dfn[py],dfn[y]);
y=fa[py],py=top[y];
}
if(dfn[x]<=dfn[y]) add(rt,dfn[x],dfn[y]);
else add(rt,dfn[y],dfn[x]);
}
void push_down(int g)
{
if(f[g].tag==) return ;
f[f[g].lc].tag+=f[g].tag;
f[f[g].rc].tag+=f[g].tag;
f[g].tag=;
}
void dfs(int g)
{
if(f[g].l==f[g].r)
{
c[f[g].d]+=f[g].tag;
return;
}
push_down(g);
dfs(f[g].lc);
dfs(f[g].rc);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&q[i]);
for(int i=;i<n;i++)
{
scanf("%d%d",&u,&v);
link[u].push_back(v);
link[v].push_back(u);
}
dfs1(,);
top[]=,dfs2(,);
build(,tot,rt);
for(int i=;i<=n;i++)
Add(q[i-],q[i]),c[q[i]]--;
dfs(rt);
for(int i=;i<=n;i++)
printf("%d\n",c[i]);
return ;
}