fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4.  
  5. #define CS			const static
  6.  
  7. //Reps
  8. #define Rep(x,l,r)		for(int x = (l) ; x <= (r) ; x++)
  9. #define Rush(X)			int ____X , X ; scanf("%d",&____X) ; for(X = 1 ; X <= ____X ; X++)
  10. #define RepNxt(x,k)		for(int k = head[x] ; k ; k = nxt[k])
  11. #define RepDec(x,l,r)		for(int x = (l) ; x >= (r) ; x--)
  12.  
  13. //SegTree
  14. #define LS(x)			((x)<<1)
  15. #define RS(x)			(((x)<<1) + 1)
  16.  
  17. using namespace std ;
  18.  
  19. CS int MaxN = 10010 , MaxE = MaxN << 1 ;
  20.  
  21. int opp[MaxE] , nxt[MaxE] ;
  22.  
  23. int val[MaxN] , head[MaxN] , dep[MaxN] , que[MaxN] , size[MaxN] , cost[MaxN] ,
  24. 	top[MaxN] , son[MaxN] , fa[MaxN] , chain[MaxN] ;
  25.  
  26. int n , tot ;
  27.  
  28. void Ins(int x,int y)
  29. {
  30. 	opp[++tot] = y ; nxt[tot] = head[x] ; head[x] = tot ;
  31. 	opp[++tot] = x ; nxt[tot] = head[y] ; head[y] = tot ;
  32. }
  33.  
  34. void HeavyLight()
  35. {
  36. 	que[1] = que[0] = 1 ; dep[1] =0 ; fa[1] = 1 ; cost[1] = 0 ;
  37. 	Rep(i,1,que[0])
  38. 	{
  39. 		int x = que[i] ;
  40. 		RepNxt(x,k)	if(opp[k] != fa[x])
  41. 		{int y = opp[k] ; que[++que[0]] = y ; dep[y] = dep[x] + 1 , fa[y] = x , cost[y] = cost[x] + val[((k+1)>>1)+1] ;}
  42. 	}
  43.  
  44. 	memset(son,0,sizeof(son)) ; memset(size,0,sizeof(size)) ; size[1] = 1 ;
  45. 	RepDec(i,que[0],2)
  46. 	{
  47. 		int x = que[i] , y = fa[x] ; size[x]++ ; size[y] += size[x] ;
  48. 		if(size[x]>size[son[y]])	son[y] = x ;
  49. 	}
  50.  
  51.  
  52. 	int cnt = 0 ;
  53. 	Rep(i,1,n)	if(son[fa[i]] != i)
  54. 	{
  55. 		chain[i] = ++cnt ; top[i] = i ;
  56. 		for(int k = son[i] ; k ; k = son[k])	top[k] = k , chain[k] = cnt ;
  57. 	}
  58. }
  59.  
  60. int Lca(int x ,int y)
  61. {
  62. 	while(chain[x] != chain[y])
  63. 	{
  64. 		if(dep[top[x]]<dep[top[y]])	swap(x,y) ;
  65. 		x = fa[top[x]] ;
  66. 	}
  67. 	return (dep[x]<dep[y])?(x):(y) ;
  68. }
  69.  
  70. void QueryDist(int x,int y)	{printf("%d\n",cost[x]+cost[y]-(cost[Lca(x,y)]<<1));}
  71.  
  72. void Kth(int x,int y)
  73. {
  74. 	int k ; scanf("%d",&k) ;
  75.  
  76. }
  77.  
  78. void Solve()
  79. {
  80. 	scanf("%d",&n);
  81.  
  82. 	tot = 0 ; memset(head,0,sizeof(head)) ;
  83. 	Rep(i,2,n)
  84. 		{int x , y ; scanf("%d %d %d\n",&x,&y,&val[i]) ; Ins(x,y) ;}
  85.  
  86. 	HeavyLight();
  87.  
  88. 	char com[10] ; int x , y , k ;
  89. 	for(scanf("%s",com) ; com[1] != 'O' ; scanf("\n%s",&com))
  90. 	{
  91. 		scanf("%d %d",&x,&y) ;
  92. 		if(com[1]=='I')	QueryDist(x,y) ;
  93. 		else		Kth(x,y) ;
  94. 	}
  95. }
  96.  
  97. int main()
  98. {
  99. 	Rush(T) Solve() ;
  100.  
  101. 	return 0 ;
  102. }
  103.  
Success #stdin #stdout 0.01s 3228KB
comments (?)
stdin
copy 
1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE
stdout
copy 
5
https://ideone.com/MB9BW
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!