题意：给你一棵树，然后有一个遍历顺序，你需要补全这个遍历顺序，然后输出这个遍历顺序中每个点的出现次数。
解题思路：本来想找树剖的题，结果发现了一题可以直接写lca的。。。。
做法1：非常简单的NOIP式做法就是tjlca后直接树上差分即可。时间效率\( O(n) \)（常数较大）.(BZOJ上1064ms）
#include <stdio.h>
#include <string.h>
#define MN 300005
#define v edge[i].to
struct link{int to,nxt;}edge[MN<<];
int cf[MN],h[MN],q[MN],a[MN],n,cnt,lca[MN],fa[MN],f[MN];
inline int in(){
int x=;bool f=; char ch=getchar();
while(ch<''||ch>'') f=ch=='-',ch=getchar();
while(ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();
return f?-x:x;
}
inline void ins(int *h,int x,int y){edge[++cnt].to=y,edge[cnt].nxt=h[x],h[x]=cnt;}
inline void insw(int x,int y){ins(h,x,y);ins(h,y,x);}
inline int getfa(int x){return fa[x]?fa[x]=getfa(fa[x]):x;}
inline void tjlca(int u){
for (register int i=h[u]; i; i=edge[i].nxt)
if (v!=f[u]) f[v]=u,tjlca(v),fa[v]=u;
for (register int i=q[u]; i; i=edge[i].nxt)
if (lca[v]) lca[v]=getfa(lca[v]);
else lca[v]=u;
}
inline void dfs(int u){
for (register int i=h[u]; i; i=edge[i].nxt)
if (v!=f[u]) dfs(v),cf[u]+=cf[v];
}
void init(){
n=in();for (int i=; i<=n; ++i) a[i]=in(),ins(q,a[i],i),ins(q,a[i],i-);
for (register int i=; i<n; ++i) insw(in(),in());
}
void solve(){
tjlca();for (register int i=; i<n; ++i)
++cf[a[i]],++cf[a[i+]],--cf[lca[i]],--cf[f[lca[i]]];dfs();
for (register int i=; i<=n; ++i) --cf[a[i]];
for (register int i=; i<=n; ++i) printf("%d\n",cf[i]);
}
int main(){init(); solve(); return ;}
做法2：用树剖代替lca，用差分序列维护剖下来的树，也可以直接AC。时间效率为\( O(n \log \log n)\) ~\(O(n \log n) \)。(BZOJ 792ms)
#include <stdio.h>
#define MN 300005
int cnt,to[MN<<],nxt[MN<<];
int head[MN],siz[MN],son[MN],dep[MN],a[MN],top[MN],fa[MN],pos[MN],n,d[MN],dfsn;
inline int in(){
int x=;bool f=; char ch=getchar();
while(ch<''||ch>'') f=ch=='-',ch=getchar();
while(ch>=''&&ch<='') x=(x<<)+(x<<)+ch-'',ch=getchar();
return f?-x:x;
}
inline void ins(int x,int y){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;}
inline void insw(int x,int y){ins(x,y);ins(y,x);};
inline void swp(int &a,int &b){a^=b^=a^=b;}
inline void dfs1(int u,int f,int d){
siz[u]=,fa[u]=f,dep[u]=d;
for (register int i=head[u]; i; i=nxt[i])
if (to[i]!=f){
dfs1(to[i],u,d+);siz[u]+=siz[to[i]];
if (siz[to[i]]>siz[son[u]]) son[u]=to[i];
}
}
inline void dfs2(int u,int tp){
top[u]=tp,pos[u]=(++dfsn);if (son[u]) dfs2(son[u],tp);
for (register int i=head[u]; i; i=nxt[i])
if (to[i]!=fa[u]&&to[i]!=son[u]) dfs2(to[i],to[i]);
}
inline void update(int x,int y){
while(top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) swp(x,y);
++d[pos[top[x]]],--d[pos[x]+];x=fa[top[x]];
}if (dep[x]>dep[y]) swp(x,y);++d[pos[x]],--d[pos[y]+];
}
void init(){
n=in();for (register int i=; i<=n; ++i) a[i]=in();
for (register int i=; i<n; ++i) insw(in(),in());
dfs1(,,);dfs2(,);
}
void solve(){
for (register int i=; i<n; ++i) {
update(a[i],a[i+]);
if (i!=) --d[pos[a[i]]],++d[pos[a[i]]+];
}--d[pos[a[n]]],++d[pos[a[n]]+];
for (register int i=; i<=n; ++i) d[i]+=d[i-];
for (register int i=; i<=n; ++i)
printf("%d\n",d[pos[i]]);
}
int main(){init(); solve(); return ;}