传送门
对于这道题，我们不难想到，对于两个点，我们可以求出他们的lca，然后顺着链暴力往上修改。
但是这样时间复杂度是很不乐观的，最多可以达到n^2。
这里介绍一种可以用来修改树上路径的方法——子树前缀和。
设定一个修改数组change。如果要对x到y路径上的所有点权值+k，lca为z。那么change[x]+=k，change[y]+=k，change[z]-=k，change[fa[z]]-=k。这样如果最后对change[i]求子树前缀和的话，最后得到的结果就是i权值的修改量。
特点：可以O(1)修改，但是只能一次性查询（因为对于一系列的询问，需要O(n)前缀和预处理）
#include<bits/stdc++.h> #define N 300005 using namespace std; int n,sx[N],first[N],tot,down[N],up[N][21],change[N]; struct node { int next,to; }edge[2*N]; inline void addedge(int x,int y) { ++tot; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } inline void dfs1(int now,int fa) { up[now][0]=fa; down[now]=down[fa]+1; for(int i=1;i<=20;i++) up[now][i]=up[up[now][i-1]][i-1]; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs1(vis,now); } } inline int lca(int x,int y) { if(down[x]<down[y]) swap(x,y); //默认x比y深; for(int i=20;i>=0;i--) { if(down[up[x][i]]>=down[y]) x=up[x][i]; } if(x==y) return x; for(int i=20;i>=0;i--) { if(up[x][i]!=up[y][i]) { x=up[x][i]; y=up[y][i]; } } return up[x][0]; } inline void dfs2(int now) { for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==up[now][0]) continue; dfs2(vis); change[now]+=change[vis]; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n; for(int i=1;i<=n;i++) { cin>>sx[i]; } for(int i=1;i<=n-1;i++) { int x,y; cin>>x>>y; addedge(x,y); addedge(y,x); } dfs1(1,0); /*This is used to debug for(int i=1;i<=n;i++) { for(int j=0;j<=20;j++) { cout<<up[i][j]<<" "; } cout<<endl; } */ for(int i=1;i<n;i++) { int x=sx[i]; int y=sx[i+1]; change[x]++; change[y]++; change[lca(x,y)]--; change[up[lca(x,y)][0]]--; } dfs2(1); for(int i=2;i<=n;i++) change[sx[i]]--;//既是终点，又是起点的点 for(int i=1;i<=n;i++) { cout<<change[i]<<'\n'; } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9458732.html
相关资源：各显卡算力对照表！