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