购物网站首页模板,服务品牌策划方案,建网站能挣钱吗,一部手机怎么做电商BZOJ3251: 树上三角形 Description 给定一大小为n的有点权树#xff0c;每次询问一对点(u,v)#xff0c;问是否能在u到v的简单路径上取三个点权#xff0c;以这三个权值为边长构成一个三角形。同时还支持单点修改。Input 第一行两个整数n、q表示树的点数和操作数第二行n个整…BZOJ3251: 树上三角形 Description 给定一大小为n的有点权树每次询问一对点(u,v)问是否能在u到v的简单路径上取三个点权以这三个权值为边长构成一个三角形。 同时还支持单点修改。 Input 第一行两个整数n、q表示树的点数和操作数 第二行n个整数表示n个点的点权 以下n-1行每行2个整数a、b表示a是b的父亲以1为根的情况下 以下q行每行3个整数t、a、b 若t0则询问(a,b) 若t1则将点a的点权修改为b n,q100000点权范围[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 Sample Output N Y Y N 题解Here! 首先容易想到一个暴力算法 若询问是xy求出LCA(x,y)暴力将这条链中所有的点权存入数组排个序暴力扫一遍。 也就是这样 bool solve(int x,int y){int lcaLCA(x,y);int top0,num[100010];num[top]val[lca];for(int ix;i!lca;ifa[i])num[top]val[i];for(int iy;i!lca;ifa[i])num[top]val[i];sort(num1,numtop1);if(top3)return false;for(int i3;itop;i)if(num[i]num[i-1]num[i-2])return true;return false;
}但是不用想就知道肯定TLE。。。 怎么办 我们注意到点权是231以内的数而判断条件是两边之和大于第三边。 两边之和大于第三边 跟某一个式子很像f[i]f[i-1]f[i-2] 这是什么斐波那契数列 在231以内数列的最大项只达到了50项。 也就是说超过50项一定存在3个数可以组成三角形 所以我们在函数头部添加一句 if(deep[x]deep[y]-2*deep[lca]50)return true;即可。 注意由于点权是231以内所以要将判断组成三角形的式子移个项不然会爆int。 附代码 #includeiostream
#includealgorithm
#includecstdio
#define MAXN 100010
using namespace std;
int n,m,c1;
int val[MAXN],head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],top[MAXN];
struct node{int next,to;
}a[MAXN1];
inline int read(){int date0,w1;char c0;while(c0||c9){if(c-)w-1;cgetchar();}while(c0c9){datedate*10c-0;cgetchar();}return date*w;
}
inline void add(int x,int y){a[c].toy;a[c].nexthead[x];head[x]c;a[c].tox;a[c].nexthead[y];head[y]c;
}
void dfs1(int rt){son[rt]0;size[rt]1;for(int ihead[rt];i;ia[i].next){int willa[i].to;if(!deep[will]){deep[will]deep[rt]1;fa[will]rt;dfs1(will);size[rt]size[will];if(size[son[rt]]size[will])son[rt]will;}}
}
void dfs2(int rt,int f){top[rt]f;if(son[rt])dfs2(son[rt],f);for(int ihead[rt];i;ia[i].next){int willa[i].to;if(will!fa[rt]will!son[rt])dfs2(will,will);}
}
int LCA(int x,int y){while(top[x]!top[y]){if(deep[top[x]]deep[top[y]])swap(x,y);xfa[top[x]];}if(deep[x]deep[y])swap(x,y);return x;
}
bool solve(int x,int y){int lcaLCA(x,y);if(deep[x]deep[y]-2*deep[lca]50)return true;int top0,num[55];num[top]val[lca];for(int ix;i!lca;ifa[i])num[top]val[i];for(int iy;i!lca;ifa[i])num[top]val[i];sort(num1,numtop1);if(top3)return false;for(int i3;itop;i)if(num[i]-num[i-1]num[i-2])return true;return false;
}
void work(){int f,x,y;while(m--){fread();xread();yread();if(f0){if(solve(x,y))printf(Y\n);else printf(N\n);}if(f1)val[x]y;}
}
void init(){int x,y;nread();mread();for(int i1;in;i)val[i]read();for(int i1;in;i){xread();yread();add(x,y);}deep[1]1;dfs1(1);dfs2(1,1);
}
int main(){init();work();return 0;
}转载于:https://www.cnblogs.com/Yangrui-Blog/p/9097139.html
