「Luogu 1501」Tree II

发表于 | | 阅读次数:
字数统计: 895 字

Description

题目链接：Luogu 1501

一棵 $n$ 个点的树，每个点的初始权值为 $1$。对于这棵树有 $q$ 个操作，每个操作为以下四种操作之一：

  • + u v c：将 $u$ 到 $v$ 的路径上的点的权值都加上 $c​$。
  • - u1 v1 u2 v2：将树中原有的边 $(u_1,v_1)$ 删除，加入一条新边 $(u_2,v_2)$，保证操作完之后仍然是一棵树。
  • * u v c：将 $u$ 到 $v$ 的路径上的点的权值都乘上 $c$。
  • / u v：询问u到v的路径上的点的权值和，求出答案对于 $51061$ 的余数。

数据范围：$1\le n,q\le 10^5$，$0\le c\le 10^4$

Solution

其实 $\text{LCT}​$ 中的懒标记下传和线段树中的是一样的，并且都是按照乘法比加法优先的原则进行的。

这里主要提几个坑点：

  1. 我们发现 $\text{mod}=51061$，但是 $\text{mod}^2=2607225721>2147483647$，因此我们要开 $\text{unsigned int}$ 或者 $\text{long long}$。
  2. 题目中没有保证操作都是合法的！也就是说 $\text{link}$ 或 $\text{cut}$ 时可能不合法，需要判断不合法情况。

时间复杂度：$O(q\log n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
#include <cstdio>
#include <algorithm>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]

const int N=1e5+5;
const unsigned int mod=51061;
int n,m,fa[N],ch[N][2],sz[N],st[N];
unsigned int val[N],sum[N],add[N],mul[N];
bool r[N];

char getc() {
    char ch=getchar();
    while(ch<'*') ch=getchar();
    return ch;
}
bool get(int x) {
    return rs(fa[x])==x;
}
bool isroot(int x) {
    return ls(fa[x])!=x&&rs(fa[x])!=x;
}
void rev(int x) {
    std::swap(ls(x),rs(x)),r[x]^=1;
}
void Mul(int x,int v) {
    (sum[x]*=v)%=mod,(val[x]*=v)%=mod,(add[x]*=v)%=mod,(mul[x]*=v)%=mod;
}
void Add(int x,int v) {
    (sum[x]+=1LL*v*sz[x]%mod)%=mod,(val[x]+=v)%=mod,(add[x]+=v)%=mod;
}
void pushup(int x) {
    sz[x]=sz[ls(x)]+sz[rs(x)]+1;
    sum[x]=(sum[ls(x)]+sum[rs(x)]+val[x])%mod;
}
void pushdown(int x) {
    if(r[x]) rev(ls(x)),rev(rs(x)),r[x]=0;
    if(mul[x]!=1) Mul(ls(x),mul[x]),Mul(rs(x),mul[x]),mul[x]=1;
    if(add[x]!=0) Add(ls(x),add[x]),Add(rs(x),add[x]),add[x]=0;
}
void rotate(int x) {
    int y=fa[x],z=fa[y],k=get(x);
    !isroot(y)&&(ch[z][get(y)]=x),fa[x]=z;
    ch[y][k]=ch[x][k^1],fa[ch[x][k^1]]=y;
    ch[x][k^1]=y,fa[y]=x;
    pushup(y),pushup(x);
}
void splay(int x) {
    int u=x,tp=0;
    st[++tp]=u;
    while(!isroot(u)) st[++tp]=u=fa[u];
    while(tp) pushdown(st[tp--]);
    while(!isroot(x)) {
        int y=fa[x];
        if(!isroot(y)) rotate(get(x)==get(y)?y:x);
        rotate(x);
    }
}
void access(int x) {
    for(int y=0;x;x=fa[y=x]) splay(x),rs(x)=y,pushup(x);
}
void makeroot(int x) {
    access(x),splay(x),rev(x);
}
int findroot(int x) {
    access(x),splay(x);
    pushdown(x);
    while(ls(x)) pushdown(x=ls(x));
    return x;
}
void split(int x,int y) {
    makeroot(x),access(y),splay(y);
}
void link(int x,int y) {
    makeroot(x);
    if(findroot(y)!=x) fa[x]=y;
}
void cut(int x,int y) {
    makeroot(x);
    if(findroot(y)==x&&fa[x]==y&&!rs(x)) fa[x]=ls(y)=0,pushup(y);
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) sz[i]=val[i]=mul[i]=1;
    for(int i=1;i<n;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        link(u,v);
    }
    while(m--) {
        char ch=getc();
        int u,v,c;
        if(ch=='+') {
            scanf("%d%d%d",&u,&v,&c);
            split(u,v),Add(v,c%mod);
        }
        if(ch=='-') {
            scanf("%d%d",&u,&v),cut(u,v);
            scanf("%d%d",&u,&v),link(u,v);
        }
        if(ch=='*') {
            scanf("%d%d%d",&u,&v,&c);
            split(u,v),Mul(v,c%mod);
        }
        if(ch=='/') {
            scanf("%d%d",&u,&v);
            split(u,v);
            printf("%u\n",sum[v]);
        }
    }
    return 0;
}
0%