bzoj3153 Sone1
内容
听说noip后要写个大数据结构题收收心。
于是就翻出来了这个诡异的题。
最近氪了个权限号，本来以为这是个权限题，结果还不是= =
Description
Sxyz里有一群sx。
在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。
为了让花老师开花，这群sx都很努力地发言。
一次xbj对树很关心，总想有一道树的好题目
所以大家就开始讨论有什么树的好操作。
为了让题目变的简单，花老师开始就规定了是有根树。
何其蛙：子树修改，加一个数什么的，显然是可做的。
Dj：换根不是超开心？
Dd：什么子树min，max也不错啊。
Zzw：链上询问min也放进去吧。
Wyk: 链max当然的吧。
Xbj：如果不能换父亲就太无聊了吧。
Gy：链加。
Monkey：链上和。
Shjj：链上修改。
Wtd：子树加。
Sone: 在线就不说什么了吧…
………….
最后大家发现有这道题目有点麻烦..都懒得写，又由于sone最近被3083的遥远的国度中lct被树剖虐暴了..就担任了出题活动…….
Input
第一行是N和M，表示有这棵树有N个点M个询问
然后是N-1行，每行x,y表示x-y有一条边
接下去是N行，每行是一个数字，表示每个点的权值
后面一行表示根
接下来是M行
第一个数字是K
K=0 表示子树修改，后面x,y，表示以x为根的子树的点权值改成y
K=1 表示换根，后面x，表示把这棵树的根变成x
K=2 表示链修改，后面x,y,z，表示把这棵树中x-y的路径上点权值改成z
K=3 表示子树询问min，后面x，表示以x为根的子树中点的权值min
K=4 表示子树询问max，后面x，表示以x为根的子树中点的权值max
K=5 表示子树加，后面x,y，表示x为根的子树中点的权值+y
K=6 表示链加，后面x,y,z，表示把这棵树中x-y的路径上点权值改成+z
K=7 表示链询问min，后面x,y，表示把这棵树中x-y的路径上点的min
K=8 表示链询问max，后面x,y，表示把这棵树中x-y的路径上点的max
K=9 表示换父亲，后面x,y，表示把x的父亲换成y，如果y在x子树里不操作。
K=10 表示链询问sum，后面x,y,z，表示表示把这棵树中x-y的路径上点的sum
K=11 表示子树询问sum，后面x，表示以x为根的子树的点权sum
Output
对于每个询问输出一个答案。
Sample Input
Input1:
5 5
2 1
3 1
4 1
5 2
4
1
4
1
2
1
10 2 3
3 1
7 3 4
6 3 3 2
9 5 1
Input2:
10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5
Sample Output
Output1:
9
1
1
Output2:
173
860
103
791
608
1557
数据范围：
N,M<=100000
中间所有的值计算在c++的int内
本来以为一个LCT就解决了，结果发现有子树？？
ETT艹下试试？胡乱推了一个ETT和LCT一起更新的东西，发现复杂度还是很资瓷的，但是感觉要写几年。
然后就学了个AAA树，感觉很不错啊。。据说还是Tarjan搞的。
大概就是把lct的虚边再搞个splay记一下，新建一些节点，让虚边的点的父亲不是虚边的点，所以所有的虚边连到的点都是这个spaly的叶子。（实在是懒得画图了
这样每个点记下链的值，虚边的值，两个加起来的值，然后每个点有个val记下值，标记是a,b，表示现在的值是a*val[pos]+b。对于lct的话，开4维，0-1是链上的，2-3是连下去的虚边，单独写个东西连和断虚边。access的时候就对照着搞下就好。
最后39s卡过了。。对我交题的时候那些被卡评测的同学说声抱歉。。
#include <cstdio>
#define inf 1e9
#define N 200010
using namespace std;
int inline read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void swap(int&a,int&b){int c=a;a=b;b=c;}
int max(int a,int b){if (a>b) return a;return b;}
int min(int a,int b){if (a<b) return a;return b;}
struct mark
{
int a,b;
mark(){a=1,b=0;}
mark(int x,int y){a=x,b=y;}
bool check(){return a!=1||b;}
mark operator + (const mark&p){return mark(a*p.a,b*p.a+p.b);}
};
int getv(int x,mark p){return x*p.a+p.b;}
struct data
{
int sum,mins,maxs,siz;
data(){sum=siz=0,mins=inf,maxs=-inf;}
data(int v){sum=mins=maxs=v,siz=1;}
data(int a,int b,int c,int d){sum=a,mins=b,maxs=c,siz=d;}
data operator + (const data&p){return data(sum+p.sum,min(mins,p.mins),max(maxs,p.maxs),siz+p.siz);}
};
data operator + (const data&p,const mark&x){return p.siz?data(p.sum*x.a+p.siz*x.b,getv(p.mins,x),getv(p.maxs,x),p.siz):p;}
int f[N],ch[N][4],sta[N],tot,rt,bin[N],bins,val[N];bool rev[N],ins[N];//0-1:chain 2-3:sub_tree ins:is a inner point
data csum[N],ssum[N],asum[N];mark cmark[N],smark[N];//csum:chain,ssum:subtree,asum:all
bool is_root(int x,int p)
{
if (p) return !f[x]||!ins[f[x]]||!ins[x];
return !f[x]||(ch[f[x]][0]!=x&&ch[f[x]][1]!=x)||ins[f[x]]||ins[x];
}
void chain_mark(int x,mark p)
{
if (!x) return;
csum[x]=csum[x]+p;
asum[x]=csum[x]+ssum[x];
val[x]=getv(val[x],p);
cmark[x]=cmark[x]+p;
}
void sub_mark(int x,mark p,int t)
{
if (!x) return;
ssum[x]=ssum[x]+p;
smark[x]=smark[x]+p;
if (!ins[x] && t)
chain_mark(x,p);
else
asum[x]=ssum[x]+csum[x];
}
void revs(int x)
{
if (!x) return;
swap(ch[x][0],ch[x][1]),rev[x]^=1;
}
void pushdown(int x)
{
if (!x) return;
if (rev[x]) revs(ch[x][0]),revs(ch[x][1]),rev[x]=0;
if (!ins[x] && cmark[x].check())
chain_mark(ch[x][0],cmark[x]),chain_mark(ch[x][1],cmark[x]),cmark[x]=mark();
if (smark[x].check())
sub_mark(ch[x][0],smark[x],0),sub_mark(ch[x][1],smark[x],0),
sub_mark(ch[x][2],smark[x],1),sub_mark(ch[x][3],smark[x],1),
smark[x]=mark();
}
void pushup(int x)
{
ssum[x]=data();
for (int i=0;i<2;i++)
if (ch[x][i])
ssum[x]=ssum[x]+ssum[ch[x][i]];
for (int i=2;i<4;i++)
if (ch[x][i])
ssum[x]=ssum[x]+asum[ch[x][i]];
if (ins[x])
csum[x]=data(),asum[x]=ssum[x];
else
{
csum[x]=data(val[x]);
for (int i=0;i<2;i++)
if (ch[x][i])
csum[x]=csum[x]+csum[ch[x][i]];
asum[x]=csum[x]+ssum[x];
}
}
void rot(int x,int p)//p:pos of son,0/2
{
int fa=f[x],fafa=f[fa],k=(ch[fa][p+1]==x)+p;
ch[fa][k]=ch[x][k^1];if (ch[x][k^1])f[ch[x][k^1]]=fa;
if (fafa) for (int i=0;i<4;i++)
if (ch[fafa][i]==fa) ch[fafa][i]=x;
f[fa]=x,ch[x][k^1]=fa,f[x]=fafa;
pushup(fa);
}
void splay(int x,int p=0)
{
int now=x,top=1;sta[top]=x;
while (!is_root(now,p)) sta[++top]=f[now],now=f[now];
while (top) pushdown(sta[top--]);
for (int fa;!is_root(x,p);rot(x,p))
if (!is_root(fa=f[x],p))
rot(((ch[f[fa]][p]==fa)^(ch[fa][p]==x))?x:fa,p);
pushup(x);
}
int new_node()
{
int x=bins?bin[bins--]:++tot;
ch[x][2]=ch[x][3]=0;ins[x]=1;
return x;
}
void set_ch(int x,int p,int y){ch[x][p]=y,f[y]=x;}
int pos(int x){for(int i=0;i<4;i++)if(ch[f[x]][i]==x)return i;return 4;}
void add(int x,int y)//add a virtual edge from a to b
{
if (!y) return;
pushdown(x);
for (int i=2;i<4;i++)
if (!ch[x][i])
{
set_ch(x,i,y);
return;
}
while(ch[x][2] && ins[ch[x][2]]) pushdown(ch[x][2]),x=ch[x][2];
int ne=new_node();
set_ch(ne,2,ch[x][2]);
set_ch(ne,3,y);
set_ch(x,2,ne);
splay(ne,2);
}
void del(int x)//del an edge between x and its inner father
{
if (!x) return;
splay(x,0);
if (!f[x]) return;
int fa=f[x];
if (ins[fa])
{
int top=1,now=fa,fafa=f[fa];sta[top]=now;
while(!is_root(now,2)) sta[++top]=f[now],now=f[now];
while(top) pushdown(sta[top--]);
if (fafa)
pushdown(ch[fa][pos(x)^1]),
set_ch(fafa,pos(fa),ch[fa][pos(x)^1]),splay(fafa,2);
bin[++bins]=fa;
}
else
ch[fa][pos(x)]=0,splay(fa,0);
f[x]=0;
}
int get_fa(int x)//find a true father,not inner
{
splay(x,0);
if (!f[x]) return 0;
if (!ins[f[x]]) return f[x];
int fa=f[x];
splay(fa,2);
return f[fa];
}
int access(int x)
{
int fa=0;
for (;x;fa=x,x=get_fa(x))
splay(x,0),del(fa),add(x,ch[x][1]),
set_ch(x,1,fa),pushup(x);
return fa;
}
int lca(int x,int y){access(x);return access(y);}
void make_root(int x){access(x),splay(x,0),revs(x);}
void link(int x,int y){make_root(x),add(y,x),access(x);}
void cut(int x){access(x),splay(x,0),f[ch[x][0]]=0,ch[x][0]=0,pushup(x);}
void update_chain(int x,int y,mark p)
{
make_root(x),access(y),splay(y,0);
chain_mark(y,p);
}
data get_chain(int x,int y)
{
make_root(x),access(y),splay(y,0);
return csum[y];
}
void update_sub(int x,mark p)
{
access(x),splay(x,0);
val[x]=getv(val[x],p);
for (int i=2;i<4;i++)
if (ch[x][i])
sub_mark(ch[x][i],p,1);
pushup(x),splay(x,0);
}
data get_sub(int x)
{
access(x),splay(x,0);
data ans=data(val[x]);
for (int i=2;i<4;i++)
if (ch[x][i])
ans=ans+asum[ch[x][i]];
return ans;
}
int x,y,z,n,m,ed[N][2];
main()
{
n=read(),m=read();
tot=n;
for (int i=1;i<n;i++)
ed[i][0]=read(),ed[i][1]=read();
for (int i=1;i<=n;i++)
val[i]=read(),pushup(i);
for (int i=1;i<n;i++)
link(ed[i][0],ed[i][1]);
rt=read(),make_root(rt);
while(m--)
{
int k=read();
if (k==0)
x=read(),y=read(),update_sub(x,mark(0,y));
else if (k==1)
rt=read(),make_root(rt);
else if (k==2)
x=read(),y=read(),z=read(),update_chain(x,y,mark(0,z)),make_root(rt);
else if (k==3)
x=read(),printf("%d\n",get_sub(x).mins);
else if (k==4)
x=read(),printf("%d\n",get_sub(x).maxs);
else if (k==5)
x=read(),y=read(),update_sub(x,mark(1,y));
else if (k==6)
x=read(),y=read(),z=read(),update_chain(x,y,mark(1,z)),make_root(rt);
else if (k==7)
x=read(),y=read(),printf("%d\n",get_chain(x,y).mins),make_root(rt);
else if (k==8)
x=read(),y=read(),printf("%d\n",get_chain(x,y).maxs),make_root(rt);
else if (k==9)
{x=read(),y=read();if(lca(x,y)==x)continue;cut(x),link(y,x),make_root(rt);}
else if (k==10)
x=read(),y=read(),printf("%d\n",get_chain(x,y).sum),make_root(rt);
else if (k==11)
x=read(),printf("%d\n",get_sub(x).sum);
}
}