洛谷P1501 [国家集训队]Tree II(LCT)
2018-06-17 20:43:27来源:未知 阅读 ()
题目描述
一棵n个点的树,每个点的初始权值为1。对于这棵树有q个操作,每个操作为以下四种操作之一:
-
+ u v c
:将u到v的路径上的点的权值都加上自然数c; -
- u1 v1 u2 v2
:将树中原有的边(u1,v1)删除,加入一条新边(u2,v2),保证操作完之后仍然是一棵树; -
\* u v c
:将u到v的路径上的点的权值都乘上自然数c; -
/ u v
:询问u到v的路径上的点的权值和,求出答案对于51061的余数。
输入输出格式
输入格式:
第一行两个整数n,q
接下来n-1行每行两个正整数u,v,描述这棵树
接下来q行,每行描述一个操作
输出格式:
对于每个/对应的答案输出一行
输入输出样例
3 2 1 2 2 3 * 1 3 4 / 1 1
4
说明
10%的数据保证,1<=n,q<=2000
另外15%的数据保证,1<=n,q<=5*10^4,没有-操作,并且初始树为一条链
另外35%的数据保证,1<=n,q<=5*10^4,没有-操作
100%的数据保证,1<=n,q<=10^5,0<=c<=10^4
By (伍一鸣)
全程自己YY,调了一下午真累啊QWQ......
LCT的板子题,要维护子树和,加法标记,乘法标记和自身的值
放标记的时候先放乘法标记
至于为什么http://www.cnblogs.com/zwfymqz/p/8588693.html
// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<cstring> #define int long long const int mod = 51061; using namespace std; const int MAXN = 1e5+10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x * f; } int N, Q; #define ls(x) T[x].ch[0] #define rs(x) T[x].ch[1] #define fa(x) T[x].f struct node { int f, ch[2], r, mul, add, siz, sum, val; }T[MAXN]; bool IsRoot(int x) { return T[fa(x)].ch[0] != x && T[fa(x)].ch[1] != x; } int ident(int x) { return T[fa(x)].ch[0] == x ? 0 : 1; } void connect(int x, int fa, int how) { T[x].f = fa; T[fa].ch[how] = x; } void update(int x) { T[x].sum = (T[ls(x)].sum + T[rs(x)].sum + T[x].val ) % mod; T[x].siz = T[ls(x)].siz + T[rs(x)].siz + 1 ; } void rotate(int x) { int Y = fa(x), R = fa(Y), Yson = ident(x), Rson = ident(Y); int B = T[x].ch[Yson ^ 1]; T[x].f = R; if(!IsRoot(Y)) connect(x, R, Rson); connect(B, Y, Yson); connect(Y, x, Yson ^ 1); update(Y);update(x); } void pushr(int x) { if(T[x].r) { swap(ls(x), rs(x)); T[ls(x)].r ^= 1; T[rs(x)].r ^= 1; T[x].r = 0; } } void pushmul(int x) { T[ls(x)].val *= T[x].mul; T[ls(x)].val %= mod; T[rs(x)].val *= T[x].mul; T[rs(x)].val %= mod; T[ls(x)].sum *= T[x].mul; T[ls(x)].sum %= mod; T[rs(x)].sum *= T[x].mul; T[rs(x)].sum %= mod; T[ls(x)].add *= T[x].mul; T[ls(x)].add %= mod; T[rs(x)].add *= T[x].mul; T[rs(x)].add %= mod; T[ls(x)].mul *= T[x].mul; T[ls(x)].mul %= mod; T[rs(x)].mul *= T[x].mul; T[rs(x)].mul %= mod; T[x].mul = 1; } void pushadd(int x) { T[ls(x)].val += T[x].add; T[ls(x)].val %= mod; T[rs(x)].val += T[x].add; T[rs(x)].val %= mod; T[ls(x)].sum += T[ls(x)].siz * T[x].add; T[ls(x)].sum %= mod; T[rs(x)].sum += T[rs(x)].siz * T[x].add; T[rs(x)].sum %= mod; T[ls(x)].add += T[x].add; T[ls(x)].add %= mod; T[rs(x)].add += T[x].add; T[rs(x)].add %= mod; T[x].add = 0; } void pushdown(int x) { pushr(x); pushmul(x); pushadd(x); } int st[MAXN]; int fuck; void splay(int x) { int y = x, top = 0; st[++top] = y; while(!IsRoot(y)) st[++top] = (y = fa(y)); while(top) pushdown(st[top--]); for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x)) if(!IsRoot(y)) rotate( ident(x) == ident(y) ? y : x ); } void access(int x) { for(int y = 0; x; x = fa(y = x))//tag splay(x), rs(x) = y, update(x); } void makeroot(int x) { access(x); splay(x); T[x].r ^= 1; } void split(int x,int y) { makeroot(x); access(y); splay(y); } void link(int x, int y) { makeroot(x); T[x].f = y; } int findroot(int x) { access(x); splay(x); while(ls(x)) x = ls(x); return x; } void cut(int x, int y) { split(x, y); //makeroot(x); if(findroot(y) == x && fa(x) == y && !rs(x)) T[x].f = T[y].ch[0] = 0, update(y); } main() { freopen("a.in","r",stdin); scanf("%lld%lld", &N, &Q); for(int i = 1; i <= N; i++) T[i].val = 1, T[i].sum = 1, T[i].mul = 1, T[i].siz = 1, T[i].add = 0; for(int i = 1; i <= N - 1; i++) { int x = read(), y = read(); link(x, y); } int fuck = 0; while(Q--) { char c = 0; int u1, v1, u2, v2, val; while(c < '*') c = getchar(); scanf("%lld%lld", &u1, &v1); if(c == '+') { scanf("%lld", &val); split(u1, v1); T[v1].val += val; T[v1].val %= mod; T[v1].add += val; T[v1].add %= mod; T[v1].sum += T[v1].siz * val; T[v1].sum %= mod; } else if(c == '-') { scanf("%lld%lld", &u2, &v2); cut(u1, v1); link(u2, v2); } else if(c == '/') { split(u1, v1); printf("%d\n",T[v1].sum%mod); } else { scanf("%lld",&val); split(u1, v1); T[v1].val *= val; T[v1].val %= mod; T[v1].sum *= val; T[v1].siz %= mod; T[v1].add *= val; T[v1].add %= mod; T[v1].mul *= val; T[v1].mul %= mod; } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash