Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <map>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- using namespace std;
- int input(){
- int res = 0, m = 1; char c = ' ';
- while (c < '0' && c != '-') c = getchar();
- if (c == '-') m = -1, c = getchar();
- while (c >= '0') res = res * 10 + (c - '0'), c = getchar();
- return res*m;
- }
- typedef long long ll;
- const int N = 1e5 + 1;
- ll a[N];
- vector <int> g[N];
- map <ll, int> cnt;
- ll sum = 0, k, f = 0;
- void dfs(int u, int p){
- if (f) return;
- sum += a[u];
- if (cnt[sum-k]){
- f = 1; return;
- }
- ++ cnt[sum];
- for (int v: g[u])
- if (v != p) dfs(v, u);
- -- cnt[sum];
- sum -= a[u];
- }
- int main(){
- for (int t = input(); t; -- t){
- int n = input();
- for (int i = 0; i < n; ++ i)
- g[i].clear();
- for (int i = 1; i < n; ++ i){
- int u = input() - 1,
- v = input() - 1;
- g[u].push_back(v),
- g[v].push_back(u);
- }
- for (int i = 0; i < n; ++ i)
- a[i] = input();
- k = input(); f = 0;
- cnt = {{0, 1}};
- dfs(0, -1);
- if (f) puts("good tree");
- else puts("bad tree");
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment