fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> edge[200005];
  5. int anc[20][200005]; // parent node
  6. int level[200005], sbtr[200005]; // depth node dan jumlah node pada subtree
  7. int in[200005], out[200005]; // buat cek subtree
  8. int visited[200005], revcutter;
  9. unordered_set<int> cutter; // cutter untuk menandai subtree yang membatasi jawaban, revcutter untuk menandai subtree yang 
  10. int lg = 18, timer, ans_dist, ans;
  11.  
  12. void dfs(int now, int par){
  13.     anc[0][now] = par; level[now] = level[par]+1;
  14.     visited[now] = 1;
  15.     in[now] = timer++;
  16.     for(int dst : edge[now]) if(dst != par) dfs(dst, now);
  17.     out[now] = timer++;
  18. }
  19.  
  20. int last_dfs(int now, int par){
  21.     int x = 1;
  22.     for(int dst : edge[now]) if(dst != par && !cutter.count(dst) && (anc[0][revcutter] != dst)) x += last_dfs(dst, now);
  23.     return x;
  24. }
  25.  
  26. void addEdge(int src, int dst){
  27.     edge[src].emplace_back(dst);
  28.     edge[dst].emplace_back(src);
  29. }
  30.  
  31. int lca(int x, int y){
  32.     if(level[x] < level[y])
  33.         swap(x,y);
  34.  
  35.     for(int i = lg; i >= 0; i--)
  36.         if((level[x] - (1 << i)) >= level[y])
  37.             x = anc[i][x];
  38.  
  39.     if(x == y) return x;
  40.  
  41.     for(int i = lg; i>=0; i--){
  42.         if(anc[i][x] != anc[i][y]){
  43.             x = anc[i][x]; y = anc[i][y];
  44.         }
  45.     }
  46.     return anc[0][x];
  47. }
  48.  
  49. int distance(int x, int y){
  50.     return level[x] + level[y] - 2 * level[lca(x,y)];
  51. }
  52.  
  53. // is y subtree of x
  54. bool isSubtree(int x, int y){
  55.     return (in[x] <= in[y] && out[x] >= out[y]);
  56. }
  57.  
  58. int solve(int x, int y){
  59.     if(x == y && !ans_dist) return x;
  60.     if(anc[18][x] != anc[18][y]) return 0;
  61.  
  62.  
  63.     bool stats = false;
  64.     int ancDepth = level[lca(x,y)];
  65.     int dist = distance(x,y);
  66.     int mid = (dist + ans_dist) >> 1, node;
  67.  
  68.     for(auto element: cutter){
  69.         if(isSubtree(element, y)){
  70.             if(dist == ans_dist) return x;
  71.             return 0;
  72.         }
  73.     }
  74.     if(revcutter && !isSubtree(revcutter, y)){
  75.         if(dist == ans_dist) return x;
  76.         return 0;
  77.     }
  78.  
  79.     if((level[x]+ans_dist+level[y])%2) {
  80.         return 0;
  81.     }
  82.  
  83.     if(ans_dist != dist){
  84.         cutter.clear();
  85.         revcutter = 0;
  86.     }
  87.     else stats = true;
  88.  
  89.     // cari dari y
  90.     if(mid == (level[y] - ancDepth)){
  91.         node = x;
  92.         int par = mid-1-ans_dist;
  93.         if(par != -1){
  94.             for(int i=lg; i>=0; i--){
  95.                 if(par & (1 << i)) 
  96.                     node = anc[i][node];
  97.             }
  98.             cutter.insert(node);
  99.         }
  100.  
  101.  
  102.         node = y;
  103.         for(int i=lg; i>=0; i--){
  104.             if((mid-1) & (1 << i)) 
  105.                 node = anc[i][node];
  106.         }
  107.         cutter.insert(node);
  108.         ans_dist = mid;
  109.     }
  110.     else {
  111.         node = (mid > (level[y]-ancDepth))? x : y;
  112.         int par = mid-1-((node == x)?ans_dist:0);
  113.         if(par != -1){
  114.             for(int i=lg; i>=0; i--){
  115.                 if(par & (1 << i)) {
  116.                     node = anc[i][node];
  117.                 }
  118.             }
  119.             cutter.insert(node);
  120.         }
  121.         revcutter = anc[0][node];
  122.         ans_dist = mid;
  123.     }
  124.     if(stats) return x;
  125.     return anc[0][node];
  126. }
  127.  
  128. int main()
  129. {
  130.     ios_base::sync_with_stdio(0);
  131.     cin.tie(0); cout.tie(0);
  132.     anc[0][0] = 0;
  133.     int n; cin >> n;
  134.     // while((1 << lg) < n)
  135.     //     lg++;
  136.     int u,v,k;
  137.     for(int i=0;i<n-1;i++) {
  138.         cin >> u >> v >> k;
  139.         if(k) addEdge(u, v);
  140.     }
  141.  
  142.     // binary lifting preprocessing
  143.     memset(visited, 0, sizeof(visited));
  144.     for(int i=1; i<=n; i++){
  145.         if(!visited[i]) dfs(i,i);
  146.     }
  147.     for(int i=1;i<=lg;i++){
  148.         for(int j=1;j<=n;j++){
  149.             anc[i][j] = anc[i-1][anc[i-1][j]];
  150.         }
  151.     }
  152.  
  153.     int q; cin >> q;
  154.     int center; // jumlah node yang memenuhi dan tumpuan penghitungan node yang memenuhi
  155.  
  156.     while(q--){
  157.         revcutter = 0, ans_dist = 0;
  158.         cutter.clear();
  159.         int peeps,x; cin >> peeps;
  160.         cin >> center;
  161.         cout << center << " ";
  162.         for(int i=0;i<(peeps-1);i++){
  163.             cin >> x; 
  164.             cout << x << " ";
  165.             if(!center){
  166.                 continue;
  167.             }
  168.             center = solve(center, x);
  169.         }
  170.         cout << ": ";
  171.         if(center){
  172.             cout << last_dfs(center, center) << '\n';
  173.         }
  174.         else cout << "0\n"; 
  175.     }
  176.  
  177.     return 0;
  178. }
Success #stdin #stdout 0.01s 27832KB
comments (?)
stdin
copy 
5
1 2 0
2 3 0
3 4 0
4 5 0
31
2 1 1
2 2 2
2 3 3
2 4 4
2 5 5
2 1 2 
3 1 2 3 
4 1 2 3 4 
5 1 2 3 4 5 
4 1 2 3 5 
3 1 2 4 
4 1 2 4 5 
3 1 2 5 
2 1 3 
3 1 3 4 
4 1 3 4 5 
3 1 3 5 
2 1 4 
3 1 4 5 
2 1 5 
2 2 3 
3 2 3 4 
4 2 3 4 5 
3 2 3 5 
2 2 4 
3 2 4 5 
2 2 5 
2 3 4 
3 3 4 5 
2 3 5 
2 4 5
stdout
copy 
1 1 : 1
2 2 : 1
3 3 : 1
4 4 : 1
5 5 : 1
1 2 : 0
1 2 3 : 0
1 2 3 4 : 0
1 2 3 4 5 : 0
1 2 3 5 : 0
1 2 4 : 0
1 2 4 5 : 0
1 2 5 : 0
1 3 : 0
1 3 4 : 0
1 3 4 5 : 0
1 3 5 : 0
1 4 : 0
1 4 5 : 0
1 5 : 0
2 3 : 0
2 3 4 : 0
2 3 4 5 : 0
2 3 5 : 0
2 4 : 0
2 4 5 : 0
2 5 : 0
3 4 : 0
3 4 5 : 0
3 5 : 0
4 5 : 0
https://ideone.com/1HS0rE
language:
C++14 (gcc 8.3)
created:
43 days 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!