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?10^5,1?c?10^4$

解題思路

LCT模板
多了兩個計算的值
在下傳lazym的時候把lazya乘上lazym即可（lazya為加值的lazy，lazym為乘值的lazy）

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #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--){cin>>c;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; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【LCT】Tree II（luogu 1501）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。