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