1 /************************************************************** 2     Problem: 3251 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:268 ms 7     Memory:5808 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12  13 using namespace std;14 typedef long long ll;15 const int N = 100005;16 const int M = 200005;17 struct edges{18     int next, to;19 }e[M];20 struct tree_node{21     int v, dep, fa;22 }tr[N];23 int first[N], q[N];24 int n, m, tot;25  26 inline int read(){27     int x = 0, sgn = 1;28     char ch = getchar();29     while (ch < ‘0‘ || ch > ‘9‘){30         if (ch == ‘-‘) sgn = -1;31         ch = getchar();32     }33     while (ch >= ‘0‘ && ch <= ‘9‘){34         x = x * 10 + ch - ‘0‘;35         ch = getchar();36     }37     return sgn * x;38 }39  40 inline void add_edge(int x, int y){41     e[++tot].next = first[x];42     first[x] = tot;43     e[tot].to = y;44 }45  46 void add_Edges(int X, int Y){47     add_edge(X, Y);48     add_edge(Y, X);49 }50  51 void dfs(int p){52     int x, y;53     for (x = first[p]; x; x = e[x].next)54         if ((y = e[x].to) != tr[p].fa){55             tr[y].fa = p, tr[y].dep = tr[p].dep + 1;56             dfs(y);57         }58 }59  60 void query(int a, int b){61     int cnt = 0, i;62     while (cnt < 50 && a != b){63         if (tr[a].dep > tr[b].dep)64             q[++cnt] = tr[a].v, a = tr[a].fa;65         else q[++cnt] = tr[b].v, b = tr[b].fa;66     }67     q[++cnt] = tr[a].v;68     if (cnt >= 50){69         puts("Y");70         return;71     }72     sort(q + 1, q + cnt + 1);73     for(i = 1; i <= cnt - 2; ++i)74         if ((ll) q[i] + q[i + 1] > q[i + 2]){75             puts("Y");76             return;77         }78     puts("N");79 }80  81 int main(){82     n = read(), m = read();83     int i, T, X, Y;84     for (i = 1; i <= n; ++i)85         tr[i].v = read();86     for (i = 1; i < n; ++i){87         X = read(), Y = read();88         add_Edges(X, Y);89     }90     dfs(1);91     for (i = 1; i <= m; ++i){92         T = read(), X = read(), Y = read();93         if (T) tr[X].v = Y; else query(X, Y);94     }95     return 0;96 }