fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <utility>
  4. #include <algorithm>
  5.  
  6. #define rep(i,j,k) for (int (i)=(j);(i)<=(k);++(i))
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11.  
  12. const int L=20,N=(int)1e5;
  13.  
  14. bool invalid[N*2+10];
  15. int st[L+10][N*20+10];
  16. int lg[N*20+10],euler[N*20+10];
  17. ll sumval[N+10],minusval[N+10];
  18. vector<pair<int,int> > e[N+10];
  19. int n,Q,mm=1,cnt,ecnt,root,total;
  20. int ed[N*2+10],nxt[N*2+10],cost[N*2+10];
  21. int fa[N+10],id[N+10],anc[N+10],dis[N+10],son[N+10],sum[N+10],size[N+10],maxson[N+10];
  22.  
  23. inline int getint(){
  24. 	int x=0;
  25. 	bool flag=false;
  26. 	char ch=getchar();
  27. 	while (!(ch>='0' && ch<='9' || ch=='-')) ch=getchar();
  28. 	if (ch=='-') flag=true,ch=getchar();
  29. 	while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  30. 	return flag?-x:x;
  31. }
  32.  
  33. inline void addedge(int x,int y,int z){
  34. 	nxt[++mm]=son[x]; son[x]=mm; ed[mm]=y; cost[mm]=z;
  35. 	nxt[++mm]=son[y]; son[y]=mm; ed[mm]=x; cost[mm]=z;
  36. }
  37.  
  38. void dfs(int x,int pre){
  39. 	euler[++ecnt]=x;
  40. 	id[x]=ecnt;
  41. 	for (int i=son[x];i;i=nxt[i])
  42. 		if (ed[i]!=pre){
  43. 			anc[ed[i]]=x;
  44. 			dis[ed[i]]=dis[x]+cost[i];
  45. 			dfs(ed[i],x);
  46. 			euler[++ecnt]=x;
  47. 		}
  48. }
  49.  
  50. void makelist(){
  51. 	rep(i,1,ecnt) st[0][i]=dis[euler[i]];
  52. 	rep(i,2,ecnt) lg[i]=lg[i-1]+(1<<lg[i-1]+1==i);
  53. 	rep(i,1,lg[ecnt]) rep(j,1,ecnt-(1<<i)+1) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<i-1)]);
  54. }
  55.  
  56. int getlca(int x,int y){
  57. 	x=id[x];
  58. 	y=id[y];
  59. 	if (x>y) swap(x,y);
  60. 	int k=lg[y-x+1];
  61. 	return min(st[k][x],st[k][y-(1<<k)+1]);
  62. }
  63.  
  64. int getdis(int x,int y){
  65. 	return dis[x]+dis[y]-2*getlca(x,y);
  66. }
  67.  
  68. void findroot(int x,int pre){
  69. 	size[x]=1;
  70. 	maxson[x]=0;
  71. 	for (int i=son[x];i;i=nxt[i])
  72. 		if (ed[i]!=pre && !invalid[i]){
  73. 			findroot(ed[i],x);
  74. 			size[x]+=size[ed[i]];
  75. 			maxson[x]=max(maxson[x],size[ed[i]]);
  76. 		}
  77. 	maxson[x]=max(maxson[x],total-size[x]);
  78. 	if (maxson[x]<maxson[root]) root=x;
  79. }
  80.  
  81. void work(int x){
  82. 	for (int i=son[x];i;i=nxt[i])
  83. 		if (!invalid[i]){
  84. 			invalid[i^1]=true;
  85. 			root=0;
  86. 			total=size[ed[i]];
  87. 			maxson[0]=size[ed[i]];
  88. 			findroot(ed[i],0);
  89. 			e[x].push_back(make_pair(ed[i],root));
  90. 			fa[root]=x;
  91. 			work(root);
  92. 		}
  93. }
  94.  
  95. inline void update(int u,int e){
  96. 	for (int i=u;i;i=fa[i]){
  97. 		sum[i]+=e;
  98. 		sumval[i]+=(ll)e*getdis(u,i);
  99. 		if (fa[i]) minusval[i]+=(ll)e*getdis(u,fa[i]);
  100. 	}
  101. }
  102.  
  103. inline ll calc(int x){
  104. 	ll ans=sumval[x];
  105. 	for (int i=x;fa[i];i=fa[i]){
  106. 		ans+=sumval[fa[i]]-minusval[i];
  107. 		ans+=(ll)(sum[fa[i]]-sum[i])*getdis(x,fa[i]);
  108. 	}
  109. 	return ans;
  110. }
  111.  
  112. inline ll query(int x){
  113. 	ll y=calc(x);
  114. 	for (vector<pair<int,int> >::iterator i=e[x].begin();i!=e[x].end();++i)
  115. 		if (calc(i->first)<y) return query(i->second);
  116. 	return y;
  117. }
  118.  
  119. int main(){
  120. 	n=getint(); Q=getint();
  121. 	rep(i,2,n){
  122. 		int x=getint(),y=getint(),z=getint();
  123. 		addedge(x,y,z);
  124. 	}
  125. 	dfs(1,0);
  126. 	makelist();
  127. 	root=0;
  128. 	total=n;
  129. 	maxson[0]=n;
  130. 	findroot(1,0);
  131. 	int start=root;
  132. 	work(root);
  133. 	while (Q--){
  134. 		int u=getint(),e=getint();
  135. 		update(u,e);
  136. 		printf("%lld\n",query(start));
  137. 	}
  138. 	return 0;
  139. }
Success #stdin #stdout 0s 261632KB
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/yhb7YX
tree, standard
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!