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;
  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.     cout << now << " ";
  26.     int x = 1;
  27.     for(int dst : edge[now]) if(dst != par && !cutter.count(dst) && (anc[0][revcutter] != dst)) x += last_dfs(dst, now);
  28.     return x;
  29. }
  30.  
  31. void addEdge(int src, int dst){
  32.     edge[src].emplace_back(dst);
  33.     edge[dst].emplace_back(src);
  34. }
  35.  
  36. int lca(int x, int y){
  37.     if(level[x] < level[y])
  38.         swap(x,y);
  39.  
  40.     for(int i = lg; i >= 0; i--)
  41.         if((level[x] - (1 << i)) >= level[y])
  42.             x = anc[i][x];
  43.  
  44.     if(x == y) return x;
  45.  
  46.     for(int i = lg; i>=0; i--){
  47.         if(anc[i][x] != anc[i][y]){
  48.             x = anc[i][x]; y = anc[i][y];
  49.         }
  50.     }
  51.     return anc[0][x];
  52. }
  53.  
  54. int distance(int x, int y){
  55.     return level[x] + level[y] - 2 * level[lca(x,y)];
  56. }
  57.  
  58. // is y subtree of x
  59. bool isSubtree(int x, int y){
  60.     return (in[x] <= in[y] && out[x] >= out[y]);
  61. }
  62.  
  63. int solve(int x, int y){
  64.     if(x == y) return x;
  65.     if(anc[18][x] != anc[18][y]) return 0;
  66.  
  67.  
  68.     bool stats = false;
  69.     int ancDepth = level[lca(x,y)];
  70.     int dist = distance(x,y);
  71.     int mid = (dist + ans_dist) >> 1, node;
  72.  
  73.     // cout << x << " " << y;
  74.     for(auto element: cutter){
  75.         if(isSubtree(element, y)){
  76.             // cout << x << " " << mid << " " << y;
  77.             if(dist == ans_dist) return x;
  78.             return 0;
  79.         }
  80.     }
  81.     if(revcutter && !isSubtree(revcutter, y)){
  82.         if(dist == ans_dist) return x;
  83.         return 0;
  84.     }
  85.  
  86.     if((level[x]+ans_dist+level[y])%2) {
  87.         // printf("\nTEST LEVEL: %d %d %d\n",level[x],ans_dist,level[y]);
  88.         return 0;
  89.     }
  90.  
  91.     if(ans_dist != dist){
  92.         cutter.clear();
  93.         revcutter = 0;
  94.     }
  95.     else stats = true;
  96.  
  97.     // printf("mid: %d ancDepth: %d\n", mid, ancDepth);
  98.     // printf("dist: %d ans_dist: %d\n", dist, ans_dist);
  99.  
  100.     // cari dari y
  101.     if(mid == (level[y] - ancDepth)){
  102.         // clock_t start = clock();
  103.         node = x;
  104.         for(int i=lg; i>=0; i--){
  105.             if((mid-1-ans_dist) & (1 << i)) 
  106.                 node = anc[i][node];
  107.         }
  108.         // clock_t end = clock();
  109.         // cout << "Waktu Eksekusi: " << double(end - start)/CLOCKS_PER_SEC << '\n';
  110.         cutter.insert(node);
  111.  
  112.  
  113.         node = y;
  114.         for(int i=lg; i>=0; i--){
  115.             if((mid-1) & (1 << i)) 
  116.                 node = anc[i][node];
  117.         }
  118.         cutter.insert(node);
  119.         ans_dist = mid;
  120.     }
  121.     else {
  122.         node = (mid > (level[y]-ancDepth))? x : y;
  123.         int par = mid-1-((node == x)?ans_dist:0);
  124.         if(par != -1){
  125.             for(int i=lg; i>=0; i--){
  126.                 if(par & (1 << i)) {
  127.                     node = anc[i][node];
  128.                 }
  129.             }
  130.             cutter.insert(node);
  131.         }
  132.         revcutter = anc[0][node];
  133.         ans_dist = mid;
  134.     }
  135.     if(stats) return x;
  136.     return anc[0][node];
  137. }
  138.  
  139. int main()
  140. {
  141.     ios_base::sync_with_stdio(0);
  142.     cin.tie(0); cout.tie(0);
  143.     anc[0][0] = 0;
  144.     int n; cin >> n;
  145.     // while((1 << lg) < n)
  146.     //     lg++;
  147.     int u,v,k;
  148.     for(int i=0;i<n-1;i++) {
  149.         cin >> u >> v >> k;
  150.         if(k) addEdge(u, v);
  151.     }
  152.  
  153.     // binary lifting preprocessing
  154.     memset(visited, 0, sizeof(visited));
  155.     for(int i=1; i<=n; i++){
  156.         if(!visited[i]) dfs(i,i);
  157.     }
  158.     for(int i=1;i<=lg;i++){
  159.         for(int j=1;j<=n;j++){
  160.             anc[i][j] = anc[i-1][anc[i-1][j]];
  161.         }
  162.     }
  163.  
  164.     // debug
  165.     // for(int i=0;i<lg;i++){
  166.     //     for(int j=1;j<=n;j++){
  167.     //         cout << anc[i][j] << " ";
  168.     //     }
  169.     //     cout << endl;
  170.     // }
  171.  
  172.     // for(int i=1;i<=n;i++){
  173.     //     printf("\nnode %d in: %d out: %d sbtr: %d", i, in[i], out[i], sbtr[i]);
  174.     // }
  175.  
  176.     int q; cin >> q;
  177.     int center; // jumlah node yang memenuhi dan tumpuan penghitungan node yang memenuhi
  178.  
  179.     while(q--){
  180.         revcutter = 0, ans_dist = 0;
  181.         cutter.clear();
  182.         int peeps,x; cin >> peeps;
  183.         cin >> center;
  184.         for(int i=0;i<(peeps-1);i++){
  185.             cin >> x; 
  186.             if(!center){
  187.                 continue;
  188.             }
  189.             center = solve(center, x);
  190.             // cout << '[';
  191.             // for(auto it:cutter) cout << it << " ";
  192.             // cout << ']' << endl;
  193.             // cout << '[' << revcutter << ']' << endl;
  194.             // cout << "center: " << center << endl;
  195.         }
  196.         // cout << '[';
  197.         // for(auto it:cutter) cout << it << " ";
  198.         // cout << ']' << endl;
  199.         // cout << '[';
  200.         // for(auto it:revcutter) cout << it << " ";
  201.         // cout << ']' << endl;
  202.         if(center){
  203.             cout << last_dfs(center, center) << '\n';
  204.         }
  205.         else puts("0");
  206.     }
  207.  
  208.     return 0;
  209. }
  210.  
  211.  
Success #stdin #stdout 0.01s 25224KB
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
3
2 9 5
2 2 10
3 3 8 4
stdout
copy 
0
0
0
https://ideone.com/bWpgvJ
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!