2014 ACM/ICPC Asia Regional Shanghai Online C - Tree —— 树上前缀和

本文主要是介绍2014 ACM/ICPC Asia Regional Shanghai Online C - Tree —— 树上前缀和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一棵树，两种操作：
1.将x到y的路径上的所有点的权值+k
2.将x到y路径上的所有边的权值+k
所有操作结束后问你所有的点权和所有的边权

题解：

这道题用树链剖分估计会T，因为它是$nlo{g}^{2}n$的。
由于每次加的一定是一条链或者两条链，那么我们只需要用前缀和的思想去做即可，也就是说加点权的时候在x的位置加上k，y的位置+k，lca的位置-k，因为x和y的值合并了之后就变成2k，需要减掉一个。然后在lca的父亲位置-k。
边权的话只需要在x，y的位置+k，lca的位置-2k即可。我们将边权当做儿子节点处理，并且这是普遍解决边权存储位置的方法。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
ll sum_p[N],sum_e[N],flag[N];
struct node
{int to,next;
}e[N*2];
int cnt,head[N];
void add(int x,int y)
{e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt++;
}
int fa[N][25],dep[N];
void dfs(int x,int f)
{fa[x][0]=f;dep[x]=dep[f]+1;for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==f)continue;dfs(ne,x);}
}
int n,m;
void deal()
{for(int j=1;(1<<j)<=n;j++)for(int i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
}
int lca(int x,int y){if(dep[x]<dep[y])swap(x,y);for(int i=20;i>=0;i--)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];if(x==y)return x;for(int i=20;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];return fa[x][0];
}
int xx[N],yy[N];
void dfs_p(int x,int f)
{for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==f)continue;dfs_p(ne,x);sum_p[x]+=sum_p[ne]-flag[ne];}
}
void dfs_e(int x,int f)
{for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==f)continue;dfs_e(ne,x);sum_e[x]+=sum_e[ne];}
}
int main()
{int t,cas=0;scanf("%d",&t);while(t--){int x,y;ll k;char op[10];scanf("%d%d",&n,&m);cnt=0;for(int i=1;i<=n;i++)sum_p[i]=sum_e[i]=flag[i]=0,head[i]=-1;for(int i=1;i<n;i++)scanf("%d%d",&xx[i],&yy[i]),add(xx[i],yy[i]),add(yy[i],xx[i]);dfs(1,0),deal();while(m--){scanf("%s%d%d%lld",op,&x,&y,&k);int l=lca(x,y);if(op[3]=='1')sum_p[x]+=k,sum_p[y]+=k,sum_p[l]-=k,flag[l]+=k;elsesum_e[x]+=k,sum_e[y]+=k,sum_e[l]-=2*k;}dfs_p(1,0),dfs_e(1,0);printf("Case #%d:\n",++cas);for(int i=1;i<=n;i++){printf("%lld",sum_p[i]);if(i==n)printf("\n");elseprintf(" ");}if(n==1)printf("\n");for(int i=1;i<n;i++){printf("%lld",dep[xx[i]]>dep[yy[i]]?sum_e[xx[i]]:sum_e[yy[i]]);if(i==n-1)printf("\n");elseprintf(" ");}}return 0;
}

这篇关于2014 ACM/ICPC Asia Regional Shanghai Online C - Tree —— 树上前缀和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---