3251: 树上三角形
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
n,q<=100000，点权范围[1,2^31-1]
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
思路：
脑洞题，考虑到MAXINT范围内完全不能构成三角形的数字有多少---Fib数列，在47项的时候爆INT，所以只要路径上有超过47个点直接输出Y，没有超过47个点可以暴力把所有点压入数组，并排序枚举相邻三个点能否构成三角形，注意存在两点相加爆INT的情况，枚举之后不满足则输出N，因为每次暴力不超过50，所以复杂度相当低。我考场上还写了一个树剖，汗。类似找LCA的过程，一层一层爬就好，记得在循环里判当前是否到47个了！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <iostream>
using namespace std;
const int N = 120000;
int fa[N],dep[N],pv[N];
int q[60];
inline char nc() {
static char buf[100000], *p1, *p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin)),p1==p2?EOF:*p1++;
}
inline int read() {
int x=0;char ch=nc();
while(!isdigit(ch))ch=nc();
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=nc();}
return x;
}
int cnt,head[N<<2],to[N<<2],next[N<<2];
inline void add_edge(int a,int b) {
to[++cnt]=b;
next[cnt]=head[a];
head[a]=cnt;
to[++cnt]=a;
next[cnt]=head[b];
head[b]=cnt;
}
void dfs1(int p) {
dep[p]=dep[fa[p]]+1;
int i;
for(i=head[p];i;i=next[i]) {
if(to[i]!=fa[p]) {
fa[to[i]]=p;
dfs1(to[i]);
}
}
}
void query(int a,int b) {
int cnt1=0;
if(dep[b]>dep[a])
swap(a,b);
while(dep[a]>dep[b]) {
q[++cnt1]=pv[a];
a=fa[a];
if(cnt1>46) {
puts("Y");
return;
}
}
while(a!=b) {
q[++cnt1]=pv[a];
q[++cnt1]=pv[b];
a=fa[a],b=fa[b];
if(cnt1>46) {
puts("Y");
return;
}
}
q[++cnt1]=pv[a];
if(cnt1>46) {
puts("Y");
return;
}
sort(q+1,q+cnt1+1);
int i;
for(i=3;i<=cnt1;i++) {
if(q[i]-q[i-2]<q[i-1]) {
puts("Y");
return;
}
}
puts("N");
}
int main() {
int n,q;
n=read(),q=read();
int i;
for(i=1;i<=n;i++)
pv[i]=read();
int x,y;
for(i=1;i<n;i++) {
x=read(),y=read();
add_edge(x,y);
}
dfs1(1);
//dfs2(1,1,1);
/*for(i=1;i<=n;i++) {
printf("%d
",len[i]);
}*/
while(q--) {
int opt=read();
if(opt) {
x=read(),y=read();
pv[x]=y;
}
else {
x=read(),y=read();
query(x,y);
}
}
}
欢迎到原博客看看 >原文链接<