fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <algorithm>
  4.  
  5. #define rep(i,j,k) for (int (i)=(j);(i)<=(k);++(i))
  6.  
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10.  
  11. const int N=(int)1e5;
  12. const ll inf=0x7f7f7f7f7f7f7f7fll;
  13.  
  14. int n,Q,mm,a[N+10],d[N+10],son[N+10],size[N+10],ed[N*2+10],nxt[N*2+10],cost[N*2+10];
  15.  
  16. inline void addedge(int x,int y,int z){
  17. 	nxt[++mm]=son[x]; son[x]=mm; ed[mm]=y; cost[mm]=z;
  18. 	nxt[++mm]=son[y]; son[y]=mm; ed[mm]=x; cost[mm]=z;
  19. }
  20.  
  21. inline int getint(){
  22. 	int x=0;
  23. 	bool flag=false;
  24. 	char ch=getchar();
  25. 	while (!(ch>='0' && ch<='9' || ch=='-')) ch=getchar();
  26. 	if (ch=='-') flag=true,ch=getchar();
  27. 	while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  28. 	return flag?-x:x;
  29. }
  30.  
  31. namespace baoli1{
  32. 	const int N=(int)5e3;
  33. 	ll f[N+10];
  34. 	void dfs1(int x,int pre){
  35. 		size[x]=a[x];
  36. 		for (int i=son[x];i;i=nxt[i])
  37. 			if (ed[i]!=pre){
  38. 				d[ed[i]]=d[x]+cost[i];
  39. 				dfs1(ed[i],x);
  40. 				size[x]+=size[ed[i]];
  41. 			}
  42. 	}
  43. 	void dfs2(int x,int pre){
  44. 		for (int i=son[x];i;i=nxt[i])
  45. 			if (ed[i]!=pre){
  46. 				f[ed[i]]=f[x]+(ll)(size[1]-2*size[ed[i]])*cost[i];
  47. 				dfs2(ed[i],x);
  48. 			}
  49. 	}
  50. 	void solve(){
  51. 		while (Q--){
  52. 			int u,e;
  53. 			scanf("%d%d",&u,&e);
  54. 			a[u]+=e;
  55. 			dfs1(1,0);
  56. 			f[1]=0;
  57. 			rep(i,2,n) f[1]+=(ll)d[i]*a[i];
  58. 			dfs2(1,0);
  59. 			ll ans=inf;
  60. 			rep(i,1,n) ans=min(ans,f[i]);
  61. 			printf("%lld\n",ans);
  62. 		}
  63. 		exit(0);
  64. 	}
  65. }
  66.  
  67. namespace baoli2{
  68. 	const ll inf=0x7f7f7f7f7f7f7f7fll;
  69. 	ll f;
  70. 	bool vis[N+10];
  71. 	int cnt,root=1,total,d[N+10],fa[N+10],id[N+10],dis[N+10],deep[N+10],head[N+10],heavy[N+10],pedge[N+10],seg[N*4+10];
  72. 	inline void update(int k){
  73. 		seg[k]=seg[k*2]+seg[k*2+1];
  74. 	}
  75. 	void modify(int k,int lc,int rc,int p,int d){
  76. 		if (lc==rc){
  77. 			seg[k]+=d;
  78. 			return;
  79. 		}
  80. 		int mid=lc+rc>>1;
  81. 		if (p<=mid) modify(k*2,lc,mid,p,d);
  82. 		else modify(k*2+1,mid+1,rc,p,d);
  83. 		update(k);
  84. 	}
  85. 	int query(int k,int lc,int rc,int l,int r){
  86. 		if (l==lc && r==rc) return seg[k];
  87. 		int mid=lc+rc>>1;
  88. 		if (r<=mid) return query(k*2,lc,mid,l,r);
  89. 		if (l>mid) return query(k*2+1,mid+1,rc,l,r);
  90. 		return query(k*2,lc,mid,l,mid)+query(k*2+1,mid+1,rc,mid+1,r);
  91. 	}
  92. 	void dfs(int x,int pre){
  93. 		size[x]=1;
  94. 		for (int i=son[x];i;i=nxt[i])
  95. 			if (ed[i]!=pre){
  96. 				fa[ed[i]]=x;
  97. 				pedge[ed[i]]=cost[i];
  98. 				deep[ed[i]]=deep[x]+1;
  99. 				dis[ed[i]]=dis[x]+cost[i];
  100. 				dfs(ed[i],x);
  101. 				size[x]+=size[ed[i]];
  102. 				if (size[ed[i]]>size[heavy[x]]) heavy[x]=ed[i];
  103. 			}
  104. 	}
  105. 	void dfs2(int x){
  106. 		id[x]=++cnt;
  107. 		vis[x]=true;
  108. 		if (!head[x]) head[x]=x;
  109. 		if (heavy[x]){
  110. 			head[heavy[x]]=head[x];
  111. 			dfs2(heavy[x]);
  112. 		}
  113. 		for (int i=son[x];i;i=nxt[i])
  114. 			if (!vis[ed[i]]) dfs2(ed[i]);
  115. 	}
  116. 	inline ll calc(int x){
  117. 		int t=fa[root]==x?total-query(1,1,n,id[root],id[root]+size[root]-1):query(1,1,n,id[x],id[x]+size[x]-1),p=fa[root]==x?pedge[root]:pedge[x];
  118. 		return f-(ll)t*p+(ll)(total-t)*p;
  119. 	}
  120. 	void move(int x){
  121. 		ll minval=inf;
  122. 		int id=0;
  123. 		for (int i=son[x];i;i=nxt[i]){
  124. 			ll t=calc(ed[i]);
  125. 			if (t<minval){
  126. 				minval=t;
  127. 				id=ed[i];
  128. 			}
  129. 		}
  130. 		if (minval<f){
  131. 			root=id;
  132. 			f=minval;
  133. 			move(root);
  134. 		}
  135. 	}
  136. 	inline int getlca(int x,int y){
  137. 		while (head[x]!=head[y])
  138. 			if (deep[head[x]]>deep[head[y]]) x=fa[head[x]]; else y=fa[head[y]];
  139. 		return deep[x]<deep[y]?x:y;
  140. 	}
  141. 	inline int dist(int x,int y){
  142. 		return dis[x]+dis[y]-2*dis[getlca(x,y)];
  143. 	}
  144. 	inline void update(int x,int y){
  145. 		total+=y;
  146. 		modify(1,1,n,id[x],y);
  147. 	}
  148. 	void solve(){
  149. 		dfs(1,0);
  150. 		dfs2(1);
  151. 		while (Q--){
  152. 			int u=getint(),e=getint();
  153. 			f+=(ll)e*dist(u,root);
  154. 			update(u,e);
  155. 			move(root);
  156. 			printf("%lld\n",f);
  157. 		}
  158. 		exit(0);
  159. 	}
  160. }
  161.  
  162. int main(){
  163. 	n=getint(); Q=getint();
  164. 	rep(i,2,n){
  165. 		int x=getint(),y=getint(),z=getint();
  166. 		addedge(x,y,z);
  167. 	}
  168. 	if (n<=5000 && Q<=2000) baoli1::solve();
  169. 	baoli2::solve();
  170. 	return 0;
  171. }
Success #stdin #stdout 0s 11880KB
comments (?)
stdin
copy 
10 5
1 2 1
2 3 1
2 4 1
1 5 1
2 6 1
2 7 1
5 8 1
7 9 1
1 10 1
3 1
2 1
8 1
3 1
4 1
stdout
copy 
0
1
4
5
6
https://ideone.com/81mQ5v
tree, baoli
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!