题目大意：一棵树，以一定顺序走完n个点，求每个点经过多少遍
可以树链剖分，也可以直接在树上做差分序列的标记
后者打起来更舒适一点。。
具体实现：
先求x,y的lca，且dep[x]<dep[y]，
如果在一棵子树下的一条链上，那么lca就是x
则g[fa[x]]–; g[y]++;
如果在一棵子树的两条分枝上，那么lca设为z
g[x]++, g[y]++, g[z]–, g[fa[z]]–
最后从叶子节点加回根节点，加法是差分序列的那种加法
因为z会加左右两边，多加了1，所以要减去。
#include<stdio.h> #include<algorithm> using namespace std; ; struct node{ int to,next; }e[maxn*]; ],w[maxn],f[maxn],tot,logn; void insert(int u, int v){ e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; } void dfs(int u, int f, int d){ dep[u]=d; fa[u][]=f; ; i<=logn; i++) fa[u][i]=fa[fa[u][i-]][i-]; for (int i=head[u]; i; i=e[i].next) ); } void lca(int u, int v){ if (dep[u]<dep[v]) swap(u,v); int x=u,y=v; while (dep[u]>dep[v]){ ; i--) if (dep[fa[u][i]]>dep[v]) u=fa[u][i]; u=fa[u][]; } if (u==v){ //在某条链上 w[fa[u][]]--; w[x]++; return; } ; i--) //在分叉口上 if (fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } u=fa[u][]; w[x]++; w[y]++; w[u]--; w[fa[u][]]--; return; } void get_ans(int u){ f[u]=w[u];// printf(" %d\n", w[u]); for (int i=head[u],v; i; i=e[i].next){ ]) continue; get_ans(e[i].to); f[u]+=f[v]; } } int main(){ scanf("%d", &n); ; i<=n; i++) scanf(; <<logn)<n) logn++; ,u,v; i<n; i++) scanf(,a[]); dfs(,,); ; i<=n; i++){ lca(a[i-],a[i]); } get_ans(a[]); ; i<=n; i++) printf(])?f[i]:f[i]-); ; }
