普通网站建设是什么,wordpress主题显示不,公司网站如何seo,网站做cpa推广引流Tree II
luogu 1501
题目大意
给出一棵树#xff0c;让你进行若干操作#xff0c;操作如下#xff1a; 1.把两个点路径上的所有点权值加k 2.把两个点路径上的所有点权值乘k 3.把一条边断开#xff0c;连上另一条边 4.查询两个点路径上的权值和
输入样例
3 2
1 2
2 3
*…Tree II
luogu 1501
题目大意
给出一棵树让你进行若干操作操作如下 1.把两个点路径上的所有点权值加k 2.把两个点路径上的所有点权值乘k 3.把一条边断开连上另一条边 4.查询两个点路径上的权值和
输入样例
3 2
1 2
2 3
* 1 3 4
/ 1 1输出样例
4数据范围
1⩽n,q⩽105,1⩽c⩽1041\leqslant n, q\leqslant 10^5, 1\leqslant c \leqslant 10^41⩽n,q⩽105,1⩽c⩽104
解题思路
LCT模板 多了两个计算的值 在下传lazym的时候把lazya乘上lazym即可lazya为加值的lazylazym为乘值的lazy
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100010
#define wyc 51061
using namespace std;
ll n, q, x, y, z, s[N], v[N], p[N], sz[N], la[N], lm[N], fa[N], son[N][2];
char c;
bool NR(ll x)
{return son[fa[x]][0] x || son[fa[x]][1] x;
}
bool IRS(ll x)
{return son[fa[x]][1] x;
}
void pushr(ll x)
{swap(son[x][0], son[x][1]);p[x] ^ 1;return;
}
void pushm(ll x, ll y)//下传乘
{lm[x] lm[x] * y % wyc;la[x] la[x] * y % wyc;//把a的乘上这样就不会有问题了s[x] s[x] * y % wyc;v[x] v[x] * y % wyc;return;
}
void pusha(ll x, ll y)
{la[x] (la[x] y) % wyc;s[x] (s[x] y * sz[x] % wyc) % wyc;v[x] (v[x] y) % wyc;return;
}
void push_down(ll x)
{if (lm[x] ! 1) pushm(son[x][0], lm[x]), pushm(son[x][1], lm[x]), lm[x] 1;if (la[x]) pusha(son[x][0], la[x]), pusha(son[x][1], la[x]), la[x] 0;if (p[x]){if (son[x][0]) pushr(son[x][0]);if (son[x][1]) pushr(son[x][1]);p[x] 0;}return;
}
void push_up(ll x)
{s[x] (s[son[x][0]] s[son[x][1]] v[x]) % wyc;sz[x] sz[son[x][0]] sz[son[x][1]] 1;return;
}
void rotate(ll x)
{ll y fa[x], z fa[y], k IRS(x), g son[x][!k];if (NR(y)) son[z][IRS(y)] x;if (g) fa[g] y;son[x][!k] y;son[y][k] g;fa[x] z;fa[y] x;push_up(y);return;
}
void push_hall(ll x)
{if (NR(x)) push_hall(fa[x]);push_down(x);return;
}
void Splay(ll x)
{push_hall(x);while(NR(x)){if (NR(fa[x]))rotate(IRS(x) IRS(y) ? fa[x] : x);rotate(x);}push_up(x);return;
}
void access(ll x)
{for (ll y 0; x; y x, x fa[x])Splay(x), son[x][1] y, push_up(x);return;
}
void make_root(ll x)
{access(x);Splay(x);pushr(x);return;
}
ll find_root(ll x)
{access(x);Splay(x);while(son[x][0]) push_down(x), x son[x][0];Splay(x);return x;
}
void Split(ll x, ll y)
{make_root(x);access(y);Splay(y);return;
}
void link(ll x, ll y)
{make_root(x);if (find_root(y) ! x) fa[x] y;return;
}
void cut(ll x, ll y)
{make_root(x);if (find_root(y) x fa[y] x !son[y][0]){fa[y] son[x][1] 0;push_up(x);}return;
}
int main()
{scanf(%lld%lld, n, q);for (ll i 1; i n; i)sz[i] lm[i] v[i] 1;for (ll i 1; i n; i){scanf(%lld%lld, x, y);link(x, y);}while(q--){cinc;if (c ){scanf(%lld%lld%lld, x, y, z);Split(x, y);pusha(y, z);}else if (c -){scanf(%lld%lld, x, y);cut(x, y);scanf(%lld%lld, x, y);link(x, y);}else if (c *){scanf(%lld%lld%lld, x, y, z);Split(x, y);pushm(y, z);}else if (c /){scanf(%lld%lld, x, y);Split(x, y);printf(%lld\n, s[y]);}}return 0;
}
