1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
| #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define N 10010 #define INF 10000000000000LL #define LL long long #define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
int n,tot,head[N],ans,root; struct edge{ int u,v,next; LL w; edge(){} edge(int __u,int __v,LL __w){ u = __u; v = __v; w = __w; } }e[2*N]; LL D; bool used[N]; LL cnt[N],up[N],Max[N],Min; int num; LL dis[N];
inline void add(int u,int v,LL w){ e[tot] = edge(u,v,w); e[tot].next = head[u]; head[u] = tot++; }
void dfs(int u,int fa){ cnt[u] = 1; Max[u] = 0; for(int k = head[u]; k != -1 ; k = e[k].next){ int v = e[k].v; if(v == fa || used[v]) continue; dfs(v,u); cnt[u] += cnt[v]; Max[u] = max(Max[u],cnt[v]); } }
void find(int rt,int u,int fa){ up[u] = cnt[rt] - cnt[u]; if(max(Max[u],up[u]) < Min){ Min = max(Max[u],up[u]); root = u; } for(int k = head[u]; k != -1; k = e[k].next){ int v = e[k].v; if(v == fa || used[v]) continue; find(rt,v,u); } }
void cal(int u,int fa,LL d){ dis[num++] = d; for(int k = head[u]; k != -1; k = e[k].next){ int v = e[k].v; LL w = e[k].w; if(v == fa || used[v]) continue; cal(v,u,d+w); } }
int solve(int rt,LL d){ num = 0; cal(rt,-1,d); sort(dis,dis+num);
int left = 0,right = num-1, i , j , res = 0; while(left < right){ if(dis[left] + dis[right] < D) left++; else if(dis[left] + dis[right] > D) right--; else{ if(dis[left] == dis[right]){ res += (right-left+1)*(right-left)/2; break; } i = left; j = right; while(dis[i] == dis[left]) i++; while(dis[j] == dis[right]) j--; res += (i-left) * (right-j); left = i; right = j; } } return res; }
void DFS(int u){ dfs(u,-1); Min = INF; find(u,u,-1); used[root] = true; ans += solve(root,0); for(int k = head[root]; k != -1; k = e[k].next){ int v = e[k].v; LL w = e[k].w; if(used[v]) continue; ans -= solve(v,w); DFS(v); } }
int main(){ while(scanf("%d",&n)!=EOF && n){ tot = 0; cl(head,-1); for(int u = 1; u <= n; u++){ int v; LL w; while(true){ scanf("%d",&v); if(v == 0) break; scanf("%lld",&w); add(u,v,w); add(v,u,w); } } while(true){ scanf("%lld",&D); if(D == 0) break; ans = 0; cl(used,false); DFS(1); if(ans > 0) puts("AYE"); else puts("NAY"); } puts("."); } return 0; }
|