题目链接:https://www.luogu.com.cn/problem/P3258
大意:从a1 走到 an,所经过的位置+1,求每个位置的值。
重点在于利用lca进行树上差分,考虑对于x走到y,令x走到公共祖先的点+1,y走到公共祖先的点+1。公共祖先只加一次,所以减去,公共祖先的祖先不参与路径,-1。
最后遍历一遍,递推求和。对于a2 - an,因为之前被当做终点了,终点会在之后+1,所以要减去。
int answer(int x, int fa){ for(int i=0;i<ve[x].size();i++){ if(ve[x][i].fi!=fa){ answer(ve[x][i].fi,x); num[x]+=num[ve[x][i].fi]; } } } void solve() { int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } int x,y; for(int i=1;i<n;i++){ cin>>x>>y; ve[x].push_back(make_pair(y,1)); ve[y].push_back(make_pair(x,1)); } dfs(1,0,0); for(int i=1;i<n;i++){ int u = a[i],v = a[i+1]; int t = lca(u,v); num[f[t][0]]--; num[t]--; num[u]++; num[v]++; } answer(1,0); for(int i=2;i<=n;i++){ num[a[i]]--; } for(int i = 1; i <=n; i++){ cout<<num[i]<<endl; } }