水果电商网站开发方案,口碑营销策划方案,wordpress中级教程,网站开发技术规范正题
P1505 题目大意
给你一棵树让你进行以下操作
1.修改一条边的权值
2.把一条链的权值取反
3.查询一条链的权值和
4.查询一条链的边权最大值
5.查询一条链的边权最小值 解题思路
把边拆成点#xff0c;然后就是lct模板了 code
#includecstdio
#include…正题
P1505 题目大意
给你一棵树让你进行以下操作
1.修改一条边的权值
2.把一条链的权值取反
3.查询一条链的权值和
4.查询一条链的边权最大值
5.查询一条链的边权最小值 解题思路
把边拆成点然后就是lct模板了 code
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 400010
using namespace std;
int n,q,x,y,z,top,d[N];
char c[10];
struct Tree
{#define ls son[x][0]#define rs son[x][1]int p[N],q[N],w[N],s[N],g[N],gg[N],mx[N],mn[N],fa[N],son[N][2];bool NR(int x){return fa[x](son[fa[x]][0]x||son[fa[x]][1]x);}bool IRS(int x){return son[fa[x]][1]x;}void push_up(int x){gg[x]g[x]|gg[ls]|gg[rs];mn[x]100000;mx[x]-100000;s[x]s[ls]s[rs]w[x];if(g[x])mn[x]mx[x]w[x];if(lsgg[ls])mn[x]min(mn[x],mn[ls]),mx[x]max(mx[x],mx[ls]);if(rsgg[rs])mn[x]min(mn[x],mn[rs]),mx[x]max(mx[x],mx[rs]);return;}void pushr(int x){p[x]^1;swap(ls,rs);return;}void pushR(int x){w[x]-w[x];s[x]-s[x];swap(mn[x],mx[x]);mn[x]-mn[x];mx[x]-mx[x];q[x]^1;return;}void push_down(int x){if(p[x]){if(ls)pushr(ls);if(rs)pushr(rs);p[x]0;}if(q[x]){if(ls)pushR(ls);if(rs)pushR(rs);q[x]0;}return;}void rotate(int x){int yfa[x],zfa[y],kIRS(x),gson[x][!k];if(NR(y))son[z][IRS(y)]x;if(g)fa[g]y;fa[x]z;fa[y]x;son[x][!k]y;son[y][k]g;push_up(y);return;}void Splay(int x){int yx;d[top]y;while(NR(y))yfa[y],d[top]y;while(top)push_down(d[top--]);while(NR(x)){if(NR(fa[x])){if(IRS(x)IRS(fa[x]))rotate(fa[x]);else rotate(x);}rotate(x);}push_up(x);return;}void access(int x){for(int y0;x;xfa[yx])Splay(x),rsy,push_up(x);return;}void make_root(int x){access(x);Splay(x);pushr(x);return;}void link(int x,int y){make_root(x);fa[x]y;return;}void Split(int x,int y){make_root(x);access(y);Splay(y);return;}
}T;
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d%d%d,x,y,z);x,y;T.w[in]z;T.g[in]1;T.link(x,in);T.link(in,y);}scanf(%d,q);while(q--){scanf(%s%d%d,c1,x,y);if (c[1]C){T.Splay(xn);T.w[xn]y;T.push_up(xn);}else if(c[1]N){x,y;T.Split(x,y);T.pushR(y);}else if(c[1]S){x,y;T.Split(x,y);printf(%d\n,T.s[y]);}else if(c[1]Mc[2]A){x,y;T.Split(x,y);printf(%d\n,T.mx[y]);}else{x,y;T.Split(x,y);printf(%d\n,T.mn[y]);}}return 0;
}
