My Blogs
P10359 [PA2024] Kolorowy las
/tuu。写了三天。
首先考虑树的形态不变怎么做，直接的想法是树分治这种东西可以做到一只或者两只 $\log$。
但是点分这种东西不太好扩展到动态树的问题。但是因为这是单点查询，所以可以不用真正的树上染色，只需要回答每个询问即可。考虑对于每个询问，考虑找到在它之前第一次给这个点染色的操作，这样这次操作就是答案。
这样就比较简单了。可以从后向前做，遇到一个查询就把它挂在点上，对于染色操作就把邻域的所有询问回答。需要维护加删标记点，查询最近的标记点，可以用 LCT 套一个 multiset 维护（multiset 用来维护轻子树的答案），总复杂度是 $\mathcal O(n\log^2n)$。
因为要 link,cut 就要换根就要 reverse，所以需要维护到链头链尾分别的最短关键点，实现有一些细节。
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
113
114
115
116
117
int n,m,q;
namespace LCT
{
namespace Splay
{
int cnt;
struct PII
{
int fi,se;
PII(int X=0,int Y=0){fi=X,se=Y;}
bool operator <(const PII x)const{return fi<x.fi||(fi==x.fi&&se<x.se);}
};
struct{int ch[2],fa,tg,v,siz;PII l,r;multiset<PII> st;}t[2000010];
vector<int> ve[200010];
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
#define fa(x) t[x].fa
#define ident(x) (x==t[fa(x)].ch[1])
#define connect(x,f,s) (t[fa(x)=f].ch[s]=x)
#define ntroot(x) (x==ls(fa(x))||x==rs(fa(x)))
inline PII operator +(const PII a,const int b){return PII(a.fi+b,a.se);}
inline PII get(PII a,PII b){return a<b?a:b;}
template<typename ...Args> inline PII get(PII a,Args...args){return get(get(args...),a);}
inline void down(int x){t[x].tg^=1,swap(t[x].l,t[x].r),swap(ls(x),rs(x));}
inline void spread(int x){if(t[x].tg)down(ls(x)),down(rs(x)),t[x].tg=0;}
inline void update(int x)
{
spread(x);
t[x].siz=t[ls(x)].siz+t[rs(x)].siz+t[x].v;
PII nw;
if(t[x].st.size())nw=*t[x].st.begin();else nw=PII(INF,0);
t[x].l=get(t[ls(x)].l,t[rs(x)].l+t[ls(x)].siz+t[x].v,nw+t[ls(x)].siz);
t[x].r=get(t[rs(x)].r,t[ls(x)].r+t[rs(x)].siz+t[x].v,nw+t[rs(x)].siz);
}
inline void rotate(int x)
{
int f=fa(x),ff=fa(f),k=ident(x);
connect(t[x].ch[k^1],f,k);
if(ntroot(f))t[ff].ch[ident(f)]=x;fa(x)=ff;
connect(f,x,k^1),update(f),update(x);
}
void pushall(int x){if(ntroot(x))pushall(fa(x));spread(x);}
void splaying(int x)
{
pushall(x);
while(ntroot(x))
{
int f=fa(x);
if(ntroot(f))ident(x)^ident(f)?rotate(x):rotate(f);
rotate(x);
}
}
}
using namespace Splay;
unordered_map<int,int> hash;
inline void access(int x)
{
for(int y=0;x;y=x,x=fa(x))
{
splaying(x);
if(rs(x))t[x].st.insert(t[rs(x)].l+t[x].v);
rs(x)=y;
if(rs(x))t[x].st.erase(t[x].st.find(t[rs(x)].l+t[x].v));
update(x);
}
}
inline void mkroot(int x){access(x),splaying(x),down(x),update(x);}
inline int findroot(int x)
{
access(x);
splaying(x),spread(x);
while(ls(x))spread(x=ls(x));
return x;
}
inline void link(int x,int y){mkroot(x),fa(x)=y,t[y].st.insert(t[x].l+t[y].v),update(y);}
inline void cut(int x,int y){mkroot(x),access(y),splaying(y),fa(x)=ls(y)=0,update(y);}
inline int newnode(int x){t[++cnt].v=x;return update(cnt),cnt;}
inline void LINK(int x,int y,int z){z=newnode(z),hash[x*n+y]=hash[y*n+x]=z,link(x,z),link(y,z);}
inline void CUT(int x,int y){int t=hash[x*n+y];cut(x,t),cut(y,t);}
}
using namespace LCT;
struct{int opt,x,y,z;}a[200010];
int ans[200010];
inline void mian()
{
read(n,m,q),cnt=n,t[0].l=t[0].r=PII(INF,0);int x,y,z;
for(int i=1;i<=m;++i)read(x,y,z),LINK(x,y,z);
for(int i=1;i<=q;++i)
{
read(a[i].opt);
if(a[i].opt==1)read(a[i].x,a[i].y,a[i].z),LINK(a[i].x,a[i].y,a[i].z);
else if(a[i].opt==2)read(a[i].x,a[i].y),a[i].z=t[hash[a[i].x*n+a[i].y]].v,CUT(a[i].x,a[i].y);
else if(a[i].opt==3)read(a[i].x,a[i].y,a[i].z);
else read(a[i].x);
}
for(int i=q;i>=1;--i)
{
if(a[i].opt==1)CUT(a[i].x,a[i].y);
else if(a[i].opt==2)LINK(a[i].x,a[i].y,a[i].z);
else if(a[i].opt==3)
{
while(mkroot(a[i].x),t[a[i].x].l.fi<=a[i].y)
{
int p=t[a[i].x].l.se;
mkroot(p);
for(auto v:ve[p])
{
ans[v]=a[i].z;
t[p].st.erase(t[p].st.find(PII(0,p)));
}
ve[p].clear(),update(p);
}
}
else ve[a[i].x].eb(i),mkroot(a[i].x),t[a[i].x].st.insert(PII(0,a[i].x)),update(a[i].x);
}
for(int i=1;i<=q;++i)if(a[i].opt==4)write(ans[i],'\n');
}