题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3251
想一想，可以发现如果答案为no，在int范围内最多只可能同时存在46个数
所以找到lca，判断下路径上的点的个数，如果大于46个就输出Yes，否则暴力判断
|
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 |
#include<bits/stdc++.h> #define MAXN 100010 typedef long long ll; using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m; int val[MAXN],fa[MAXN][22],deep[MAXN],a[MAXN],tot=0; vector<int>v[MAXN]; void dfs(int x){ deep[x]=deep[fa[x][0]]+1; for(int i=1; i<=20; i++)fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=0; i<v[x].size(); i++){ int to=v[x][i]; if(to==fa[x][0])continue; dfs(to); } } int lca(int x,int y){ if(deep[x]>deep[y])swap(x,y); int num=deep[y]-deep[x]; for(int i=20; i>=0; i--){ if(num>=(1<<i)){ y=fa[y][i]; num-=(1<<i); } } if(x!=y){ for(int i=20; i>=0; i--){ if(fa[x][i]!=fa[y][i]){ x=fa[x][i]; y=fa[y][i]; } } x=fa[x][0]; } return x; } void solve(){ sort(a+1,a+1+tot); for(int i=3; i<=tot; i++){ if((ll)a[i]<(ll)a[i-1]+a[i-2]){ puts("Y"); return; } } puts("N"); } int main(){ n=rd(),m=rd(); for(int i=1; i<=n; i++)val[i]=rd(); for(int i=1; i<n; i++){ int x=rd(),y=rd(); fa[y][0]=x; v[x].push_back(y); v[y].push_back(x); } dfs(1); while(m--){ int x=rd(),y=rd(),z=rd(); if(x==1)val[y]=z; else{ int xx=lca(y,z); if(deep[y]+deep[z]-deep[xx]*2+1>46)puts("Y"); else{ tot=0; while(y!=xx){a[++tot]=val[y];y=fa[y][0];} while(z!=xx){a[++tot]=val[z];z=fa[z][0];} a[++tot]=val[xx]; solve(); } } } return 0; } |
