Submit: 667 Solved: 275
[Submit][Status][Discuss]
Description
给定一大小为n的有点权树,每次询问一对点(u,v),问是否能在u到v的简单路径上取三个点权,以这三个权值为边长构成一个三角形。同时还支持单点修改。
Input
第一行两个整数n、q表示树的点数和操作数
第二行n个整数表示n个点的点权
以下n-1行,每行2个整数a、b,表示a是b的父亲(以1为根的情况下)
以下q行,每行3个整数t、a、b
若t=0,则询问(a,b)
若t=1,则将点a的点权修改为b
Output
对每个询问输出一行表示答案,“Y”表示有解,“N”表示无解。
Sample Input
5 5
1 2 3 4 5
1 2
2 3
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3
1 2 3 4 5
1 2
2 3
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3
Sample Output
N
Y
Y
N
Y
Y
N
HINT
对于100%的数据,n,q<=100000,点权范围[1,231-1]
Solution
这题点权范围为Int,我们发现不能构成三角形的数列为菲波那切数列(1,1,2,3,5……),所以到第47项时已经超过了Int,所以我们当点的个数大于47个时(代码里写的是50),就可以直接输出Y了。否则我们便暴力即可。
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 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int N=100100; int n,q,a[N],tot,fa[N],Next[N],head[N],tree[N],dep[N],b[100]; bool visit[N]; void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } void dfs(int x,int depth) { visit[x]=true;dep[x]=depth; for (int i=head[x];i;i=Next[i]) if (!visit[tree[i]]) dfs(tree[i],depth+1); } void Work(int u,int v) { int tot=0; while (tot<=50&&u!=v) { if (dep[u]>dep[v]) b[++tot]=a[u],u=fa[u]; else b[++tot]=a[v],v=fa[v]; } b[++tot]=a[u]; if (tot>=50) { printf("Y\n");return;} sort(b+1,b+tot+1); for (int i=1;i<=tot-2;i++) if ((long long)b[i]+b[i+1]>b[i+2]) { printf("Y\n");return;} printf("N\n"); } int main() { scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) scanf("%d",&a[i]); tot=0; for (int i=1;i<=n-1;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y);fa[y]=x; } for (int i=1;i<=n;i++) visit[i]=false; dfs(1,1); for (int i=1;i<=q;i++) { int k,x,y; scanf("%d%d%d",&k,&x,&y); if (k==0) Work(x,y);else a[x]=y; } return 0; } |