fork download 
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define ls (id<<1)
  4. #define rs ((id<<1)|1)
  5. using namespace std;
  6. const int N=1e6+5;
  7. int cnt=0,n,m,a[N],x,y,z,fa[N],son[N],sz[N],dep[N],top[N],dfn[N],mp[N],U,V,op;
  8. vector<int> to[N];
  9. void dfs1(int u,int F,int d) {
  10. 	dep[u]=d,sz[u]++,fa[u]=F;
  11. 	for(auto v:to[u]) {
  12. 		if(v!=F) {
  13. 			dfs1(v,u,d+1);
  14. 			sz[u]+=sz[v];
  15. 			if(sz[v]>sz[son[u]]) son[u]=v;
  16. 		}
  17. 	}
  18. }
  19. void dfs2(int u,int t) {
  20. 	dfn[u]=++cnt,mp[cnt]=a[u],top[u]=t;
  21. 	if(son[u]) dfs2(son[u],t);
  22. 	for(auto v:to[u]) if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
  23. }
  24. struct node {
  25. 	int l,r,tag,sum,lma,rma,ma;
  26. 	node(){
  27. 		l=r=tag=sum=lma=rma=ma=0;
  28. 	}
  29. } t[N<<2];
  30. void upd(int id,int x) {
  31. 	t[id].tag=x;
  32. 	t[id].sum=(t[id].r-t[id].l+1)*t[id].tag;
  33. 	t[id].lma=t[id].rma=t[id].ma=t[id].sum;
  34. }
  35. void psd(int id) {
  36. 	upd(ls,t[id].tag),upd(rs,t[id].tag);
  37. 	t[id].tag=0;
  38. }
  39. void merge(node &a,node b,node c) {
  40. 	a.sum=b.sum+c.sum;
  41. 	a.lma=max(b.lma,c.ma+b.sum);
  42. 	a.rma=max(c.rma,b.rma+c.sum);
  43. 	a.ma=max(max(b.ma,c.ma),b.rma+c.lma);
  44. 	a.tag=0;
  45. }
  46. void bld(int id,int l,int r) {
  47. 	t[id].l=l,t[id].r=r;
  48. 	if(l==r) {
  49. 		t[id].sum=mp[l];
  50. 		t[id].lma=t[id].rma=t[id].ma=t[id].sum;
  51. 		return ;
  52. 	}
  53. 	int mid=(l+r)/2;
  54. 	bld(ls,l,mid);
  55. 	bld(rs,mid+1,r);
  56. 	merge(t[id],t[ls],t[rs]);
  57. }
  58. void add(int id,int l,int r,int k) {
  59. 	if(l<=t[id].l&&t[id].r<=r) {
  60. 		upd(id,k);
  61. 		return ;
  62. 	}
  63. 	if(t[id].tag) psd(id);
  64. 	if(l<=t[ls].r) add(ls,l,r,k);
  65. 	if(r>=t[rs].l) add(rs,l,r,k);
  66. 	merge(t[id],t[ls],t[rs]);
  67. }
  68. node qry(int id,int l,int r) {
  69. 	if(l<=t[id].l&&t[id].r<=r) return t[id];
  70. 	if(t[id].tag) psd(id);
  71. 	node res;
  72. 	if(l>t[ls].r) return qry(rs,l,r);
  73. 	if(r<t[rs].l) return qry(ls,l,r);
  74. 	merge(res,qry(ls,l,r),qry(rs,l,r));
  75. 	return res;
  76. }
  77. void Add1(int x,int y,int k) {
  78. 	while(top[x]!=top[y]) {
  79. 		if(dep[top[x]]<dep[top[y]]) swap(x,y);
  80. 		add(1,dfn[top[x]],dfn[x],k);
  81. 		x=fa[top[x]];
  82. 	}
  83. 	if(dep[x]>dep[y])swap(x,y);
  84. 	add(1,dfn[x],dfn[y],k);
  85. }
  86. node Qry1(int x,int y) {
  87. 	node t1,t2,ans;
  88. 	while(top[x]!=top[y]){
  89. 		if(dep[top[x]]<dep[top[y]]){
  90. 			merge(t2,qry(1,dfn[top[y]],dfn[y]),t2);
  91. 			y=fa[top[y]];
  92. 		}else{
  93. 			merge(t1,qry(1,dfn[top[x]],dfn[x]),t1);
  94. 			x=fa[top[x]];
  95. 		}
  96. 	}
  97. 	if(dep[x]>dep[y]) merge(t1,qry(1,dfn[y],dfn[x]),t1);
  98. 	else merge(t2,qry(1,dfn[x],dfn[y]),t2);
  99. 	swap(t1.lma,t1.rma);
  100. 	merge(ans,t1,t2);
  101. 	return ans;
  102. }
  103. signed main() {
  104. 	cin>>n;
  105. 	for(int i=1; i<=n; i++) cin>>a[i];
  106. 	for(int i=1; i<n; i++) cin>>U>>V,to[U].push_back(V),to[V].push_back(U);
  107. 	for(int i=1; i<=n; i++) reverse(to[i].begin(),to[i].end());
  108. 	dfs1(1,0,1),dfs2(1,1),bld(1,1,n);
  109. 	cin>>m;
  110. 	for(int i=1; i<=m; i++) {
  111. 		cin>>op;
  112. 		if(op==1) cin>>x>>y,cout<<max(0ll,Qry1(x,y).ma)<<endl;
  113. 		else cin>>x>>y>>z,Add1(x,y,z);
  114. 	}
  115. 	return 0;
  116. }
Success #stdin #stdout 0.05s 259888KB
comments (?)
stdin 
5
-3 -2 1 2 3
1 2
2 3
1 4
4 5
3
1 2 5
2 3 4 2
1 2 5
stdout 
5
9
https://ideone.com/PFvesc
language:
C++14 (gcc 8.3)
created:
6 hours 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!