fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4.  
  5. const int mod = 1e9+7;
  6. vector< set<int> > v;//The actual graph
  7. vector<int> par, level, sub;//par[i]==parent of node i in centroid tree, level[i] = level of node i in centroid tree, sub[i] = number of nodes in subarray of i
  8. vector< vector<int> > ans;//ans[i][j]==max wt edge in path from i to j
  9. map< pair<int, int>, int > m;//m[{u, v}] = wieght of edge {u, v}
  10. map<int, pair<int, int> > rank;//index of {u, v} edge
  11. int root;//First centroid of original tree.
  12. void dfsinit(int u, int p)
  13. {
  14.     sub[u] = 1;
  15.     for(int i: v[u])
  16.     {
  17.         if(i==p)continue;
  18.         dfsinit(i, u);
  19.         sub[u]+=sub[i];
  20.     }
  21. }
  22. int findcentroid(int u, int p, int root)
  23. {
  24.     int ret = u;
  25.     for(int i: v[u])
  26.     {
  27.         if(i==p)continue;
  28.         if(sub[i]>=sub[root]/2.)
  29.             ret = findcentroid(i, u, root);
  30.     }
  31.     return ret;
  32. }
  33. void dfs(int u, int p, int lvl, int maxans)
  34. {
  35.  
  36.     ans[lvl][u] = max(ans[lvl][u], maxans);
  37.     for(int i: v[u])
  38.     {
  39.         if(i==p)continue;
  40.         dfs(i, u, lvl, max(maxans, m[{i, u}]));
  41.     }
  42. }
  43. void decompose(int u, int p, int lvl)
  44. {
  45. 	dfsinit(u, -1);
  46. 	int centroid = findcentroid(u, -1, u);
  47. 	if(u==0)root = centroid;
  48. 	par[centroid] = p;
  49. 	level[centroid] = lvl;
  50. 	dfs(centroid, -1, lvl, 0);
  51. 	for(int i: v[centroid])
  52. 	{
  53. 		v[i].erase(centroid);
  54. 		decompose(i, centroid, lvl+1);
  55. 		v[i].insert(centroid);
  56. 	}
  57. }
  58. int query(int a, int b)
  59. {
  60. 	int ta = a, tb = b, lcs;
  61. 	if(level[ta]>level[tb])
  62. 		swap(ta, tb);
  63. 	while(level[ta]<level[tb])
  64. 		tb = par[tb];
  65. 	while(ta!=tb)
  66. 		ta = par[ta], tb = par[tb];
  67. 	lcs = ta;
  68. 	return max(ans[level[lcs]][a], ans[level[lcs]][b]);
  69. }
  70.  
  71. main()
  72. {
  73.     ios_base::sync_with_stdio(0);
  74.     cin.tie(0);
  75.     cout.tie(0);
  76.  
  77.     int n;
  78.     cin>>n;
  79.     v.resize(n);
  80.     par.resize(n);
  81.     sub.resize(n);
  82.     level.resize(n);
  83.     ans.resize(20, vector<int>(n));
  84.     for(int i = 0;i<n-1;i++)
  85.     {
  86.     	int x, y, c;
  87.     	cin>>x>>y>>c;
  88.     	m[{x-1, y-1}] = m[{y-1, x-1}] = c;
  89.     	v[x-1].insert(y-1);
  90.     	v[y-1].insert(x-1);
  91.     }
  92.     decompose(0, -1, 1);
  93.     //test the centroid tree formed, printing i and parent of i inc entroid tree
  94.     for(int i = 0;i<n;i++)
  95. 	cout<<i<<" "<<par[i]<<endl;
  96.     int q = 0;//Take number of queries
  97.     cin>>q;
  98.     while(q--)
  99.     {
  100.     	int a, b;
  101.     	cin>>a>>b;
  102.     	cout<<query(a-1, b-1)<<endl;
  103.     }
  104.  
  105.  
  106.  
  107.     return 0;
  108. }
Success #stdin #stdout 0s 15248KB
comments ()
stdin
copy 
15
1 2 1
1 3 3
2 4 6
2 5 9
2 6 8
3 7 7
3 8 10
4 9 2
4 10 1
4 11 4
7 12 8
7 13 6
8 14 2
8 14 3
5
4 8
5 7
9 14
1 12
6 13
stdout
copy 
0 2
1 -1
2 1
3 1
4 1
5 1
6 2
7 13
8 3
9 3
10 3
11 6
12 6
13 2
14 0
10
9
10
8
8
https://ideone.com/ub6Gc7
language:
C++14 (gcc 8.3)
created:
7 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!