fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define endl "\n"
  5. #define task "gay tay cung to"
  6. using namespace std;
  7. ll n,q;
  8. vector<ll>ke[200009];
  9. ll heavy[200009],siz[200009],depth[200009],par[200009];
  10. void dfs(ll u,ll prev)
  11. {
  12.     depth[u]=depth[prev]+1;
  13.     par[u]=prev;
  14.     ll mxsiz=0;
  15.     siz[u]=1;
  16.     for(auto i:ke[u])
  17.     {
  18.         if(i!=prev)
  19.         {
  20.             dfs(i,u);
  21.             siz[u]+=siz[i];
  22.             if(mxsiz<siz[i])
  23.             {
  24.                 mxsiz=siz[i];
  25.                 heavy[u]=i;
  26.             }
  27.         }
  28.     }
  29. }
  30. ll head[200009],pos[200009],t=0,rg[200009];
  31. void hld(ll u,ll prev)
  32. {
  33.     head[u]=prev;
  34.     pos[u]=++t;
  35.     rg[u]=t;
  36.     if(heavy[u]!=0) hld(heavy[u],prev);
  37.     for(auto i:ke[u]) if(i!=heavy[u]&&i!=par[u]) hld(i,i);
  38.     for(auto i:ke[u]) if(i!=par[u]) rg[u]=max(rg[u],rg[i]);
  39. }
  40.  
  41. ll segtree[800009],lazy[800009];
  42. void passdown(ll id)
  43. {
  44. 	ll t=lazy[id];
  45. 	segtree[id*2]+=t;
  46. 	lazy[id*2]+=t;
  47. 	segtree[id*2+1]+=t;
  48. 	lazy[id*2+1]+=t;
  49. 	lazy[id]=0;
  50. }
  51. void update(ll id,ll l,ll r,ll u,ll v,ll val)
  52. {
  53. 	if(l>v||r<u) return;
  54. 	if(l>=u&&r<=v)
  55. 	{
  56. 		segtree[id]+=val;
  57. 		lazy[id]+=val;
  58. 		return;
  59. 	}
  60. 	passdown(id);
  61. 	ll mid=(l+r)/2;
  62. 	update(id*2,l,mid,u,v,val);
  63. 	update(id*2+1,mid+1,r,u,v,val);
  64. 	segtree[id]=max(segtree[id*2],segtree[id*2+1]);
  65. }
  66. ll get(ll id,ll l,ll r,ll u,ll v)
  67. {
  68. 	if(l>v||r<u) return 0;
  69. 	if(l>=u&&r<=v) return segtree[id];
  70. 	passdown(id);
  71. 	ll mid=(l+r)/2;
  72. 	return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
  73. }
  74.  
  75. void add(ll x,ll y,ll val)
  76. {
  77. 	while(head[x]!=head[y])
  78. 	{
  79. 		if(depth[head[x]]<depth[head[y]]) swap(x,y);
  80. 		update(1,1,n,pos[head[x]],pos[x],val);
  81. 		x=par[head[x]];
  82. 	}
  83. 	if(depth[x]<depth[y]) swap(x,y);
  84. 	update(1,1,n,pos[y],pos[x],val);
  85. }
  86. ll query(ll x,ll y)
  87. {
  88. 	ll res=0;
  89. 	while(head[x]!=head[y])
  90. 	{
  91. 		if(depth[head[x]]<depth[head[y]]) swap(x,y);
  92. 		res=max(res,get(1,1,n,pos[head[x]],pos[x]));
  93. 		x=par[head[x]];
  94. 	}
  95. 	if(depth[x]<depth[y]) swap(x,y);
  96. 	res=max(res,get(1,1,n,pos[y],pos[x]));
  97. 	return res;
  98. }
  99. int main()
  100. {
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(nullptr);
  103.     cout.tie(nullptr);
  104.     if(fopen(task".inp","r"))
  105.     {
  106.         freopen(task".inp","r",stdin);
  107.         freopen(task".out","w",stdout);
  108.     }
  109.     cin>>n>>q;
  110.     for(ll i=1;i<n;i++)
  111.     {
  112.     	ll x,y;
  113.     	cin>>x>>y;
  114.     	ke[x].push_back(y);
  115.     	ke[y].push_back(x);
  116.     }
  117.     dfs(1,0);
  118.     hld(1,1);
  119.     while(q--)
  120.     {
  121.     	ll x,y,z,type;
  122.     	cin>>type>>x;
  123.     	if(type==4)
  124.     	{
  125.     		cout<<get(1,1,n,pos[x],rg[x])<<endl;
  126.     		continue;
  127.     	}
  128.     	cin>>y;
  129.     	if(type==1)
  130.     	{
  131.     		cin>>z;
  132.     		add(x,y,z);
  133.     	}
  134.     	else if(type==2) update(1,1,n,pos[x],rg[x],y);
  135.     	else if(type==3) cout<<query(x,y)<<endl;
  136.     }
  137. }
Success #stdin #stdout 0.01s 14812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NvUhzW
language:
C++14 (gcc 8.3)
created:
1 day 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!