Luogu P3258
题意就是对于一棵树，要求按照给出的顺序对每一个节点进行访问，记录每一个节点被经过的次数；特别地，我们认为只有从一个节点往外走才能被认为是经过一次。（最后一句话非常重要，仔细理解题意）
前置知识：树链剖分，差分。
最开始看到这道题我是打算使用树链剖分+线段树来做的。
但是我发现这个答案只需要每一个房间的糖果数……也就是说只需要区间修改+单点查询。
如果使用线段树的话，可能造成大量的空间浪费，而且常数也不小。
所以，我选择了使用树链剖分+差分进行统计。
由于差分写得比较少，本人卡了好一会。
大致思路如下：对于\(a[i-1]\)和\(a[i]\)两个节点，利用树链剖分求出两者之间的路径。
其实就是树剖求\(LCA\),每次比较两点的链头深度，深度大的往上跳，直至两点位于同一重链上。
把经过的每一个点权\(+1\)，终点会被重复统计，所以每一次处理完毕都要让终点\(-1\)。
#include<cstdio>
#include<algorithm>
using namespace std;
struct data
{
int to,next;
}e[600005];
int head[300005],cnt,size[300005],fa[300005],d[300005],top[300005];
int a[300005],ans[3000005],id[300005],tim,wson[300005],n;
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int u,int f,int de)
{
size[u]=1;
fa[u]=f;
d[u]=de;
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if (v==f) continue;
dfs1(v,u,de+1);
size[u]+=size[v];
if (size[wson[u]]<size[v]) wson[u]=v;
}
}
void dfs2(int u,int t)
{
top[u]=t;
id[u]=++tim;
if (wson[u]) dfs2(wson[u],t);
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if (v==fa[u]||v==wson[u]) continue;
dfs2(v,v);
}
}
void lca(int x,int y)
{
if (d[top[x]]<d[top[y]]) swap(x,y);
while (top[x]!=top[y])
{
if (d[top[x]]<d[top[y]]) swap(x,y);
ans[id[top[x]]]+=1;ans[id[x]+1]-=1;
x=fa[top[x]];
}
if (d[x]<d[y]) swap(x,y);
ans[id[y]]+=1;ans[id[x]+1]-=1;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
for (int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs1(1,0,1);
dfs2(1,1);
for (int i=2;i<=n;i++)
{
lca(a[i],a[i-1]);
ans[id[a[i]]]--;
ans[id[a[i]]+1]++;
//注意dfs序和原编号的映射关系
}
for (int i=1;i<=n;i++)
ans[i]+=ans[i-1];//用差分数组求出答案数组
for (int i=1;i<=n;i++) printf("%d\n",ans[id[i]]);
return 0;
}