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], people[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 = 19, timer, ans_dist, peeps, n;
  15.  
  16. void dfs(int now, int par){
  17.     anc[0][now] = par; level[now] = level[par]+1;
  18.     visited[now] = 1;
  19.     for(int dst : edge[now]) if(dst != par) dfs(dst, now);
  20. }
  21.  
  22. void addEdge(int src, int dst){
  23.     edge[src].emplace_back(dst);
  24.     edge[dst].emplace_back(src);
  25. }
  26.  
  27. int lca(int x, int y){
  28.     if(level[x] < level[y])
  29.         swap(x,y);
  30.  
  31.     for(int i = lg; i >= 0; i--)
  32.         if((level[x] - (1 << i)) >= level[y])
  33.             x = anc[i][x];
  34.  
  35.     if(x == y) return x;
  36.  
  37.     for(int i = lg; i>=0; i--){
  38.         if(anc[i][x] != anc[i][y]){
  39.             x = anc[i][x]; y = anc[i][y];
  40.         }
  41.     }
  42.     return anc[0][x];
  43. }
  44.  
  45. int distance(int x, int y){
  46.     if(anc[lg][x] != anc[lg][y]) return -1;
  47.     return level[x] + level[y] - 2 * level[lca(x,y)];
  48. }
  49.  
  50. int last_dfs(int now, int par){
  51.     visited[now] = 1;
  52.     int x = 0;
  53.     ans_dist = distance(now, people[0]);
  54.     int i;
  55.     if(ans_dist != -1){
  56.         // printf("kota %d: %d ", now, ans_dist);
  57.         for(i=1;i<peeps;i++){
  58.             // printf("%d ", distance(people[i],now));
  59.             if(ans_dist != distance(people[i], now)) break;
  60.         }
  61.         // puts("");
  62.         if(i == peeps) x++;
  63.     }
  64.     for(int dst : edge[now]) if(dst != par) x += last_dfs(dst, now);
  65.     return x;
  66. }
  67.  
  68. int solve(){
  69.     memset(visited, 0, sizeof(visited));
  70.     int ans = 0;
  71.     for(int i=1; i<=n; i++){
  72.         if(!visited[i]) {
  73.             ans += last_dfs(i,i);
  74.         }
  75.     }
  76.     return ans;
  77. }
  78.  
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(0);
  82.     cin.tie(0); cout.tie(0);
  83.     cin >> n;
  84.     // while((1 << lg) < n)
  85.     //     lg++;
  86.     int u,v,k;
  87.     for(int i=0;i<n-1;i++) {
  88.         cin >> u >> v >> k;
  89.         if(k) addEdge(u, v);
  90.     }
  91.  
  92.     // binary lifting preprocessing
  93.     memset(visited, 0, sizeof(visited));
  94.     for(int i=1; i<=n; i++){
  95.         if(!visited[i]) dfs(i,i);
  96.     }
  97.     for(int i=1;i<=lg;i++){
  98.         for(int j=1;j<=n;j++){
  99.             anc[i][j] = anc[i-1][anc[i-1][j]];
  100.         }
  101.     }
  102.  
  103.     int q; cin >> q;
  104.  
  105.     while(q--){
  106.         cin >> peeps;
  107.         for(int i=0;i<(peeps);i++){
  108.             cin >> people[i];
  109.             cout << people[i] << " ";
  110.         }
  111.         cout << ": " << solve() << '\n';
  112.     }
  113.  
  114.     return 0;
  115. }
  116.  
  117.  
Success #stdin #stdout 0.01s 27624KB
comments (?)
stdin
copy 
5
1 2 1
1 3 1
2 4 1
2 5 1
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 : 5
2 2 : 5
3 3 : 5
4 4 : 5
5 5 : 5
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 : 2
1 4 5 : 1
1 5 : 2
2 3 : 1
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 : 3
https://ideone.com/FavNBc
language:
C++14 (gcc 8.3)
created:
84 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!