松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。
松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，......，最后到an，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。
维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
第一行一个整数n，表示房间个数第二行n个整数，依次描述a1-an
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。
一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。
个人感觉是一道树剖比较基础的练习题。
首先直接建边，然后按照（a1, a2）……（ai, ai+1）的路径进行路径加1，最后输出时只需注意除了点a1, a2~an-1都被加了两遍，an最后不用放糖，所以再输出时，将除了a1外的所有答案减一。
代码：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
#define MAXN 600100
int x=0;
int read()
{
int f=1; x=0;char s=getchar();
while(s<‘0‘||s>‘9‘){if(s==‘-‘) f=-1;s=getchar();}
while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} x*=f;
return x;
}
int n, m, cnt, a[MAXN], flag[MAXN], dep[MAXN], son[MAXN], fa[MAXN], top[MAXN];
int w[MAXN], rev[MAXN], tot, size[MAXN], cnt2;
struct node
{
int v;
node *next;
}pool[2*MAXN], *h[MAXN];
void addedge(int u, int v)
{
node *p = &pool[++cnt], *q = &pool[++cnt];
p->v = v; p->next = h[u]; h[u] = p;
q->v = u; q->next = h[v]; h[v] = q;
}
void dfs1(int u)
{
flag[u] = 1;
size[u] = 1;
int Max=0, maxp=0;
for(node *p = h[u]; p; p = p->next)
{
if(flag[p->v] == 0)
{
dep[p->v] = dep[u] + 1;
fa[p->v] = u;
dfs1(p->v);
size[u] += size[p->v];
if(Max < size[p->v]) Max = size[p->v], maxp = p->v;
}
}
son[u] = maxp;
}
void dfs2(int u)
{
flag[u] = 0;
w[u] = ++tot;
rev[tot] = u;
if(son[u])
{
top[son[u]] = top[u];
dfs2(son[u]);
}
for(node *p = h[u]; p; p = p->next)
{
if(flag[p->v] == 1)
{
top[p->v] = p->v;
dfs2(p->v);
}
}
}
struct edge
{
int left, right, sum, lazy;
edge *ch[2];
}pool2[2*MAXN], *root;
void buildtree(edge *p, int left, int right)
{
p->left = left; p->right = right;
if(left == right) return ;
int mid = (left + right) / 2;
edge *lson = &pool2[++cnt2], *rson = &pool2[++cnt2];
p->ch[0] = lson; p->ch[1] = rson;
buildtree(lson, left, mid);
buildtree(rson, mid+1, right);
}
void push(edge *p)
{
if(p->lazy == 0 || p->lazy < 0) return ;
if(p->ch[0]) p->ch[0]->lazy += p->lazy;
if(p->ch[1]) p->ch[1]->lazy += p->lazy;
p->sum += (p->right - p->left + 1) * p->lazy;
p->lazy = 0;
}
void change(edge *p, int left, int right)
{
push(p);
if(p->left == left && p->right == right)
{
p->lazy++;
return ;
}
push(p);
if(p->ch[0]->right >= right) change(p->ch[0], left, right);
else if(p->ch[1]->left <= left) change(p->ch[1], left, right);
else change(p->ch[0], left, p->ch[0]->right), change(p->ch[1], p->ch[1]->left, right);
if(p->ch[0]) push(p->ch[0]);
if(p->ch[1]) push(p->ch[1]);
p->sum = p->ch[0]->sum + p->ch[1]->sum;
}
int query(edge *p, int left, int right)
{
push(p);
if(p->left == left && p->right == right) return p->sum;
if(p->ch[0]->right >= right) return query(p->ch[0], left, right);
else if(p->ch[1]->left <= left) return query(p->ch[1], left, right);
}
void modify(int x, int y)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
change(root, w[top[x]], w[x]);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
change(root, w[x], w[y]);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) a[i] = read();
int u, v;
for(int i=1;i<=n-1;i++)
{
u = read(); v = read();
addedge(u, v);
}
dep[1] = 1;
dfs1(1);
top[1] = 1;
dfs2(1);
root = &pool2[++cnt2];
buildtree(root, 1, n);
for(int i=1;i<=n-1;i++)//按顺序进行修改
{
modify(a[i], a[i+1]);
}
for(int i=1;i<=n;i++)
{
int ans1 = query(root, w[i], w[i]);
if(i != a[1]) ans1--;//除了a[1]之外答案都需要减一，去重
printf("%d\n",ans1);
}
return 0;
}原文：https://www.cnblogs.com/tuihuaddeming/p/11623345.html