fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<int>Adj[100001];
  6. int begin1[100001];
  7. int end1[100001];
  8. int discover[100001];
  9. int level[100001];
  10. int dp[320][100001];
  11. bool visited[100001];
  12. long long int dp1[320];
  13. long long int val_stored[320];
  14. int dfs_time=0;
  15. int SQRT_N=0;
  16.  
  17. int DFS(int u,int p,int l)
  18. {
  19. 	visited[u]=true;
  20. 	begin1[u]=dfs_time;
  21. 	level[u]=l;
  22. 	discover[dfs_time]=u;
  23. 	end1[u]=1;
  24. 	dfs_time++;
  25.  
  26. 	for(vector<int>::iterator it=Adj[u].begin();it!=Adj[u].end();it++)
  27. 	{
  28. 		if(!visited[(*it)])
  29. 		{
  30. 			end1[u]=end1[u]+DFS((*it),u,l+1);
  31. 		}
  32. 	}
  33.  
  34. 	return end1[u];
  35. }
  36.  
  37. void update_start(int index,int level1)
  38. {
  39. 	dp[index/SQRT_N][level1]=dp[index/SQRT_N][level1]+1;
  40. }
  41.  
  42. void update_new(int level1,long long int val1,int n)
  43. {
  44. 	int i=0;
  45. 	dp1[level1]=dp1[level1]+val1;
  46. 	while(i<=n)
  47. 	{
  48. 		val_stored[i/SQRT_N]=val_stored[i/SQRT_N]+dp[i/SQRT_N][level1]*val1;
  49. 		i=i+SQRT_N;
  50. 	}
  51. }
  52.  
  53. long long int query(int l,int h)
  54. {
  55. 	long long int ans=0;
  56. 	int i=l;
  57. 	//printf("(%d,%d)->  ",l,h);
  58. 	while((i)%SQRT_N!=0 && i<=h)
  59. 	{
  60. 		ans=ans+dp1[level[discover[i]]];
  61. 		//printf("%lld-_- ",dp1[level[discover[i]]]);
  62. 		i++;
  63. 	}
  64. 	while((i+SQRT_N)<=h)
  65. 	{
  66. 		ans=ans+val_stored[i/SQRT_N];
  67. 		//printf("%lld_-_ ",val_stored[i/SQRT_N]);
  68. 		i=i+SQRT_N;
  69. 	}
  70. 	while(i<=h)
  71. 	{
  72. 		ans=ans+dp1[level[discover[i]]];
  73. 		//printf("%lld-_-/ ",dp1[level[discover[i]]]);
  74. 		i++;
  75. 	}
  76. 	//printf("\n");
  77. 	return ans;
  78. }
  79.  
  80. int main()
  81. {
  82. 	int n,m;
  83. 	scanf("%d%d",&n,&m);
  84. 	SQRT_N=sqrt(n);
  85. 	//printf("%d\n",SQRT_N);
  86.  
  87. 	for(int i=1;i<n;i++)
  88. 	{
  89. 		int a,b;
  90. 		scanf("%d%d",&a,&b);
  91. 		Adj[a].push_back(b);
  92. 	}
  93.  
  94. 	DFS(1,1,0);
  95.  
  96. 	for(int i=1;i<=n;i++)
  97. 	{
  98. 		update_start(begin1[i],level[i]);
  99. 		//printf("%d %d... %d\n",begin1[i],end1[i],discover[i]);
  100. 	}
  101.  
  102. 	for(int i=0;i<m;i++)
  103. 	{
  104. 		int type;
  105. 		scanf("%d",&type);
  106.  
  107. 		if(type==1)
  108. 		{
  109. 			int l;
  110. 			long long int y;
  111. 			scanf("%d%lld",&l,&y);
  112. 			update_new(l,y,n);
  113. 		}
  114. 		else
  115. 		{
  116. 			int x;
  117. 			scanf("%d",&x);
  118. 			long long int ans=query(begin1[x],begin1[x]+end1[x]-1);
  119. 			printf("%lld\n",ans);
  120. 		}
  121. 	}
  122. return 0;}
Runtime error #stdin #stdout 0s 130944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4fE40H
language:
C++14 (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!