首页 > 代码库 > hihocoder1238 Total Highway Distance（树形dp）
hihocoder1238 Total Highway Distance（树形dp）
题意：
给定一颗有N个节点的带权树，之后进行M次操作：
Q操作：询问树上所有点对之间的距离之和
E操作：修改树上某一条边的权值
思路：
树形dp求出每条边被利用的次数并统计
然后修改的时候就把这个边权修改并将改变值乘上利用次数更改ans
/* ***********************************************Author :devil************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <cmath>#include <stdlib.h>#define inf 0x3f3f3f3f#define LL long long#define rep(a,b) for(int i=a;i<b;i++)#define dec(a,b) for(int i=a;i>=b;i--)#define ou(a) printf("%d\n",a)#define pb push_back#define mkp make_pairtemplate<class T>inline void rd(T &x){char c=getchar();x=0;while(!isdigit(c))c=getchar();while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();}}#define IN freopen("in.txt","r",stdin);#define OUT freopen("out.txt","w",stdout);using namespace std;const int mod=1e9+7;const int N=1e5+10;int n,m,x,y,w,sum[N],val[N],level[N];LL ans;char s[10];vector<pair<int,int> >eg[N];void dfs(int u,int lev,int pre){ sum[u]=1; level[u]=lev; rep(0,eg[u].size()) { int v=eg[u][i].first; if(v==pre) continue; val[v]=eg[u][i].second; dfs(v,lev+1,u); sum[u]+=sum[v]; ans+=(LL)val[v]*sum[v]*(n-sum[v]); }}int main(){ //IN rd(n);rd(m); rep(1,n) { rd(x),rd(y),rd(w); eg[x].pb(mkp(y,w)); eg[y].pb(mkp(x,w)); } dfs(1,1,1); while(m--) { scanf("%s",s); if(s[0]==‘Q‘) printf("%lld\n",ans); else { rd(x),rd(y),rd(w); if(level[x]<level[y]) swap(x,y); ans+=(LL)(w-val[x])*sum[x]*(n-sum[x]); val[x]=w; } } return 0;}
hihocoder1238 Total Highway Distance（树形dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。