传送门
一道动态树好题。
- 这道题让我想了很久的是，下放同值的操作和下放增量的操作哪个先呢？
回答：先下放同值。
为什么？因为如果一个点被赋了同值标记，那么它的增量要归零。（覆盖了）
所以当一个点既有同值标记，又有增量标记时，应先下放同值标记给儿子。 - 还有一个需要注意的是：对x~y进行处理，把那条路径取出后，应该先更新一下根的值。
细节有点多，重点看代码.
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define g g()
#define lc tr[x].son[0]
#define rc tr[x].son[1]
using namespace std;
const int N=1e5+10,inf=1<<30,size=1<<25;
char buf[size],*p1=buf,*p2=buf;
char g{return p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++;}
void qr(int &x)
{
char c=g;bool v=x=0;
while(!(isdigit(c)||c=='-'))c=g;
if(c=='-')v=1,c=g;
while(isdigit(c))x=x*10+c-'0',c=g;
if(v)x=-x;
}
void write(int x)
{
if(x/10)write(x/10);
putchar(x%10+'0');
}
void pri(int x)
{
if(x<0)putchar('-'),x=-x;
write(x);
}
struct node
{
int f,son[2],d,c,lazy,ad,w1,c1,w2,c2;bool v;
//lazy为同值标记，ad为增量标记，w1为最大值,c1为最大值在子树中的出现次数，w2,c2描述次大值
}tr[N];
inline void pushup(int d,int c,int x)//上传信息
{
if(d==-inf)return;
if(d>tr[x].w1)tr[x].w2=tr[x].w1,tr[x].c2=tr[x].c1,tr[x].w1=d,tr[x].c1=c;
else if(d==tr[x].w1)tr[x].c1+=c;
else if(d>tr[x].w2)tr[x].w2=d,tr[x].c2=c;
else if(d==tr[x].w2)tr[x].c2+=c;
}
void update(int x)//更新信息
{
tr[x].c=tr[lc].c+tr[rc].c+1;
tr[x].w1=tr[x].d;tr[x].c1=1;tr[x].w2=-inf;
if(lc)pushup(tr[lc].w1,tr[lc].c1,x),pushup(tr[lc].w2,tr[lc].c2,x);
if(rc)pushup(tr[rc].w1,tr[rc].c1,x),pushup(tr[rc].w2,tr[rc].c2,x);
}
void fz(int x)//翻转
{
tr[x].v=0;swap(lc,rc);
tr[lc].v^=1;tr[rc].v^=1;
}
void wh(int x,int y)//下放同值标记
{
if(!x)return;
tr[x].d=tr[x].lazy=y;
tr[x].w1=y;tr[x].c1=tr[x].c;
tr[x].w2=-inf;
tr[x].ad=0;//清空之前的增加标记
}
void same(int x)
{
wh(lc,tr[x].lazy);
wh(rc,tr[x].lazy);
tr[x].lazy=-inf;//lazy要设为无穷小，不能为0
}
void add(int x,int y)//下放增量标记
{
if(!x)return;
tr[x].d+=y;tr[x].ad+=y;
tr[x].w1+=y;if(tr[x].w2!=-inf)tr[x].w2+=y;
}
void increase(int x)
{
add(lc,tr[x].ad);
add(rc,tr[x].ad);
tr[x].ad=0;
}
bool rt(int x){return tr[tr[x].f].son[0]!=x&&tr[tr[x].f].son[1]!=x;}//是否为根
void dfs(int x)//递归维护
{
if(!rt(x))dfs(tr[x].f);
if(tr[x].v)fz(x);
if(tr[x].lazy!=-inf)same(x);
if(tr[x].ad!=0)increase(x);
}
void rotate(int x,int w)//旋转
{
int f=tr[x].f,ff=tr[f].f,r,R;
r=tr[x].son[w];R=f;tr[R].son[1-w]=r;if(r)tr[r].f=R;
r=x;R=ff;if(tr[R].son[0]==f)tr[R].son[0]=r;else if(tr[R].son[1]==f)tr[R].son[1]=r;tr[r].f=R;
r=f;R=x;tr[R].son[w]=r;tr[r].f=R;update(f);update(x);
}
void splay(int x)
{
dfs(x);
while(!rt(x))
{
int f=tr[x].f;
if(rt(f))rotate(x,tr[f].son[0]==x);
else
{
int ff=tr[f].f,a=(tr[f].son[0]==x),b=(tr[ff].son[0]==f);
if(a^b)rotate(x,a),rotate(x,b);
else rotate(f,a),rotate(x,a);
}
}
}
void access(int x){for(int y=0;x;x=tr[y=x].f)splay(x),rc=y,update(x);}
void makeroot(int x){access(x);splay(x);tr[x].v^=1;}
void split(int x,int y){makeroot(y);access(x);splay(x);}
void link(int x,int y){makeroot(x);tr[x].f=y;access(x);}
void cut(int x,int y){split(x,y);lc=tr[y].f=0;update(x);}
void query(int x,int y){
split(x,y);
if(tr[x].w2==-inf)puts("ALL SAME");
else pri(tr[x].w2),putchar(' '),pri(tr[x].c2),puts("");
}
int main()
{
int T,n,m,op,x,y,d;
qr(T);
for(int kk=1;kk<=T;kk++){
qr(n);qr(m); //f,son[2], d, c,lazy,ad, w1, c1,w2,c2,v;
for(int i=1;i<=n;i++)qr(tr[i].d),tr[i]=(node){0,{0,0},tr[i].d,1,-inf,0,tr[i].d,1,-inf,0,0};
for(int i=1;i<n;i++)
qr(x),qr(y),link(x,y);
printf("Case #%d:
",kk);
while(m--){
qr(op);qr(x);qr(y);
switch(op){
case 1:cut(x,y);qr(x);qr(y);link(x,y);break;
case 2:qr(d);split(x,y);wh(x,d);break;//先给一个点更新，使得将来上面的点能确定下面的信息
case 3:qr(d);split(x,y);add(x,d);break;
case 4:query(x,y);break;
}
}
}
return 0;
}