ccbeginner

TNFSHOJ 563

Oct 21st, 2020
540
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define SZ(X) (int)(X).size()
  5.  
  6. int n, m;
  7. vector<int> edges[200001];
  8. int ans[200001];
  9.  
  10. int dfs(int u, int pre){
  11.     int cnt = 1;
  12.     ans[u] = 1;
  13.     for(int i = 0; i < SZ(edges[u]); ++i){
  14.         int nxt = edges[u][i];
  15.         if(nxt == pre)continue;
  16.         int val = dfs(nxt, u);
  17.         ans[u] += val * cnt;
  18.         cnt += val;
  19.     }
  20.     ans[u] += cnt * (n-cnt);
  21.     ans[u] = ans[u] * 2 - 1;
  22.     return cnt;
  23. }
  24.  
  25. int32_t main(){
  26.     scanf("%lld", &n);
  27.     for(int i = 1; i < n; ++i){
  28.         int a,b;
  29.         scanf("%lld%lld", &a, &b);
  30.         edges[a].emplace_back(b);
  31.         edges[b].emplace_back(a);
  32.     }
  33.     dfs(1, -1);
  34.     scanf("%lld", &m);
  35.     while(m--){
  36.         int x;
  37.         scanf("%lld", &x);
  38.         printf("%lld ", n*n-ans[x]);
  39.     }
  40.     printf("\n");
  41.     return 0;
  42. }
RAW Paste Data