fork download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<vector>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. #define MAX 10020
  8. #define MAXLVL 15
  9. #define pii pair<int,int>
  10. #define rl(x) scanf("%d",&x)
  11. int dp[MAXLVL+1][MAX+20],depth[MAXLVL+1],dist[MAX],parent[MAX];
  12. vector<pii>G[MAX+12];
  13. void dfs(int cur,int par)
  14. {
  15. 	int sz=G[cur].size();
  16. 	for(int i=0;i<sz;i++)
  17. 	{
  18. 		if(G[cur][i].first!=par)
  19. 		{
  20. 			dist[G[cur][i].first]=dist[cur]+G[cur][i].second;
  21. 			parent[G[cur][i].first]=cur;
  22. 			dfs(G[cur][i].first,cur);
  23. 		}
  24. 	}
  25. }
  26. int LCA(int u,int v)
  27. {
  28. 	if(depth[u]<depth[v])
  29. 	swap(u,v);
  30. 	int diff=depth[u]-depth[v];
  31. 	for(int i=0; i<MAXLVL; i++) 
  32. 	if( (diff>>i)&1 ) 
  33. 	{
  34. 		u = dp[i][u];
  35. 	}
  36. 	if(u == v) 
  37. 	return u;
  38. 	for(int i=MAXLVL-1; i>=0; i--) 
  39. 	if(dp[i][u] != dp[i][v]) 
  40. 	{
  41. 		u = dp[i][u];
  42. 		v = dp[i][v];
  43. 	}
  44. 	return dp[0][u];
  45. }
  46. int getK(int p , int q , int k)
  47. {
  48. 	int a = LCA(p,q) , d ;
  49. 	if( a == p )
  50. 	{
  51. 		d = depth[q] - depth[p] + 1 ;
  52.         	swap(p,q); 
  53.         	k = d - k + 1 ;
  54.     	}
  55.     	else if( a == q ) ; 
  56.     	else 
  57. 	{
  58.         	if(k>depth[p]-depth[a]+1) 
  59. 		{ 
  60.         	    d = depth[p] + depth[q] - 2 * depth[a] + 1 ;
  61.         	    k = d - k + 1 ;
  62.         	    swap(p,q);
  63.         	}
  64.         	else;
  65.     	}
  66.         int lg ; 
  67. 	for( lg = 1 ; (1 << lg) <= depth[p] ; ++lg ); lg--;
  68.         k--;
  69.         for( int i = lg ; i >= 0 ; i-- )
  70. 	{
  71.             if( (1 << i) <= k )
  72. 	    {
  73.             p = dp[i][p];
  74.             k -= ( 1 << i );
  75.            }
  76.         }
  77.     return p;
  78. }
  79. void reset()
  80. {
  81. 	for(int i=0;i<MAX;i++)
  82. 	G[i].clear();
  83. 	memset(depth,0,sizeof depth);
  84. 	for(int i=1;i<MAX;i++)
  85. 	parent[i]=i,dist[i]=0;
  86. 	parent[0]=-1;
  87. }
  88. int main()
  89. {
  90. 	int t,n;
  91. 	rl(t);
  92. 	while(t--)
  93. 	{
  94. 		int u,v,w;
  95. 		rl(n);
  96. 		reset();
  97. 		for(int i=0;i<n-1;i++)
  98. 		{
  99. 			rl(u),rl(v),rl(w);
  100. 			u--,v--;
  101. 			G[u].push_back(pii(v,w));
  102. 			G[v].push_back(pii(u,w));
  103. 			depth[v]=depth[u]+1;
  104. 		}
  105. 		parent[0]=-1;
  106. 		dfs(0,-1);
  107. 		for(int i=0;i<MAXLVL;i++)
  108. 		   for(int j=0;j<n;j++)
  109. 		       dp[i][j]=-1;
  110. 		for(int i=0;i<n;i++)
  111. 		   dp[0][i]=parent[i];
  112. 		for(int i=1;i<MAXLVL;i++)
  113. 		    for(int j=0;j<n;j++)
  114. 			if(dp[i-1][j]!=-1)
  115. 			  dp[i][j] = dp[i-1][dp[i-1][j]];
  116. 		while(1)
  117. 		{
  118. 			string s;
  119. 			int x,y,z;
  120. 			cin>>s;
  121. 			if(s[1]=='I')
  122. 			{
  123. 			rl(x),rl(y);
  124. 			x--,y--;
  125. 			printf("%d\n",dist[x]+dist[y]-2*dist[LCA(x,y)]);
  126. 			}		
  127. 			else if(s[1]=='T')
  128. 			{
  129. 			rl(x),rl(y),rl(z);
  130. 			x--,y--;
  131. 			cout<<getK(x,y,z)+1<<endl;
  132.  
  133.  
  134. 			}
  135. 			else
  136. 			break;
  137.  
  138. 		}
  139. 	}
  140.  
  141.  
  142. }
Success #stdin #stdout 0s 3648KB
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
3
https://ideone.com/svhHtv
language:
C++ 4.3.2 (gcc-4.3.2)
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!