「Luogu 1501」Tree II

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%