Guest User

Untitled

a guest
Feb 18th, 2018
206
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.19 KB | None | 0 0
  1. #include <map>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7. int input(){
  8.     int res = 0, m = 1; char c = ' ';
  9.     while (c < '0' && c != '-') c = getchar();
  10.     if (c == '-') m = -1, c = getchar();
  11.     while (c >= '0') res = res * 10 + (c - '0'), c = getchar();
  12.     return res*m;
  13. }
  14. typedef long long ll;
  15. const int N = 1e5 + 1;
  16.  
  17. ll a[N];
  18. vector <int> g[N];
  19. map <ll, int> cnt;
  20. ll sum = 0, k, f = 0;
  21. void dfs(int u, int p){
  22.     if (f) return;
  23.     sum += a[u];
  24.     if (cnt[sum-k]){
  25.         f = 1; return;
  26.     }
  27.     ++ cnt[sum];
  28.     for (int v: g[u])
  29.         if (v != p) dfs(v, u);
  30.     -- cnt[sum];
  31.     sum -= a[u];
  32. }
  33. int main(){
  34.     for (int t = input(); t; -- t){
  35.         int n = input();
  36.         for (int i = 0; i < n; ++ i)
  37.             g[i].clear();
  38.         for (int i = 1; i < n; ++ i){
  39.             int u = input() - 1,
  40.                 v = input() - 1;
  41.             g[u].push_back(v),
  42.             g[v].push_back(u);
  43.         }
  44.         for (int i = 0; i < n; ++ i)
  45.             a[i] = input();
  46.         k = input(); f = 0;
  47.         cnt = {{0, 1}};
  48.         dfs(0, -1);
  49.         if (f) puts("good tree");
  50.         else puts("bad tree");
  51.     }
  52. }
Advertisement
Add Comment
Please, Sign In to add comment