3153: Sone1
Time Limit: 40 Sec Memory Limit: 256 MB
Submit: 511 Solved: 202
[Submit][Status][Discuss]
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内
APIO期间由于实在无聊开的神坑题，从APIO开始到闭幕4天时间，终于把这道题给干掉了。
Toptree是什么？我咋知道。某日yy出某方法，即把LCT的一个节点的信息加上其虚边连向的链的信息，一层一层往上就可以统计子树信息了。然后hja告诉我这个就是Toptree，只不过如果虚边用链表存会被菊花图卡掉。改成平衡树维护即可。
确实不难嘛，就是lct再加一个平衡树。
然后我就SB的用SBT来作为平衡树，然而我并没有写过SBT的标记下放。即SBT在rotate函数中也需要调用down()，就这个问题调了我一天的时间。另外标记到底是什么的问题同样调了一天，最后一天的时间解决的问题只有在n>=10的时候才会出现，大概是当一个结点不存在虚边，那么我们就不能在赋值时改变他的子树信息（因为他根本没有子树）
对了，运行时间光荣垫底。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cassert>
using namespace std;
#define MAXN 100010
#define MAXT 100010
#define INF 0x3f3f3f3f
#ifdef debug
#define Plog(...) printf(__VA_ARGS__)
#else
#define Plog(...)
#endif
int n,m;
int troot;
void make_tree(int now,int v);
void make_chain(int now,int v);
void make_splus(int now,int v);
void make_cplus(int now,int v);
struct toptree_node
{
int ch[];
int pnt;
bool rev;
int val;
int sroot;
int splus,cplus,smake,cmake;
int csum,ssum;
int cmx,cmn;
int smx,smn;
int siz;
int dsiz;
}tpt[MAXT];
int stack[MAXT],tops=-;
int topt=;
struct SBTree
{
int L[MAXT],R[MAXT],S[MAXT],V[MAXT];
int G[MAXT];
int vmx[MAXT],vmn[MAXT],sum[MAXT],siz[MAXT],pls[MAXT],mkv[MAXT];
int stack[MAXN],tops;
int topt;
SBTree()
{
tops=-;
topt=;
vmx[]=-INF;
vmn[]=INF;
}
void update(int now)
{
vmx[now]=max(max(tpt[V[now]].cmx,tpt[V[now]].smx),max(vmx[L[now]],vmx[R[now]]));
vmn[now]=min(min(tpt[V[now]].cmn,tpt[V[now]].smn),min(vmn[L[now]],vmn[R[now]]));
sum[now]=sum[L[now]]+sum[R[now]]+tpt[V[now]].ssum+tpt[V[now]].csum;
siz[now]=siz[L[now]]+siz[R[now]]+tpt[V[now]].siz+tpt[V[now]].dsiz;
S[now]=S[L[now]]+S[R[now]]+;
}
void Tree_make(int now,int v)
{
mkv[now]=v;
sum[now]=v*siz[now];
pls[now]=;
vmx[now]=vmn[now]=v;
}
void Tree_plus(int now,int delta)
{
vmx[now]+=delta;
vmn[now]+=delta;
sum[now]+=delta*siz[now];
pls[now]+=delta;
}
void down(int now)
{
if (mkv[now]!=INF)
{
Plog("SBT DOWN %d\n",G[now]);
make_tree(V[now],mkv[now]);
make_chain(V[now],mkv[now]);
if (L[now])Tree_make(L[now],mkv[now]);
if (R[now])Tree_make(R[now],mkv[now]);
mkv[now]=INF;
}
if (pls[now])
{
make_splus(V[now],pls[now]);
make_cplus(V[now],pls[now]);
if (L[now])Tree_plus(L[now],pls[now]);
if (R[now])Tree_plus(R[now],pls[now]);
pls[now]=;
}
}
void l_rotate(int &now)
{
down(now);//!!!
down(R[now]);//!!!
int t=R[now];
R[now]=L[t];update(now);
L[t]=now;update(t);
now=t;
}
void r_rotate(int &now)
{
down(now);//!!!
down(L[now]);//!!!
int t=L[now];
L[now]=R[t];update(now);
R[t]=now;update(t);
now=t;
}
void maintain(int &now)
{
if (S[L[L[now]]]>S[R[now]])
{
r_rotate(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
}
if (S[R[R[now]]]>S[L[now]])
{
l_rotate(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
}
if (S[L[R[now]]]>S[L[now]])
{
r_rotate(R[now]);
l_rotate(now);
maintain(L[now]);
maintain(R[now]);
maintain(now);
}
if (S[R[L[now]]]>S[R[now]])
{
l_rotate(L[now]);
r_rotate(now);
maintain(R[now]);
maintain(L[now]);
maintain(now);
}
}
void Insert(int &now,int val,int id)
{
if (!now)
{
if (tops==-)
now=++topt;
else
now=stack[tops--];
L[now]=R[now]=;
V[now]=val;
G[now]=id;
mkv[now]=INF;
pls[now]=;
update(now);
return ;
}
assert(val!=V[now]);
down(now);
if (val<V[now])
Insert(L[now],val,id);
else
Insert(R[now],val,id);
update(now);
maintain(now);
}
void Erase(int &now,int val)
{
assert(now);
down(now);
if (val==V[now])
{
if (!L[now])
{
stack[++tops]=now;
now=R[now];
//if (now)update(now);
}else if (!R[now])
{
stack[++tops]=now;
now=L[now];
//if (now)update(now);
}else
{
l_rotate(now);
Erase(L[now],val);
update(now);
maintain(now);
}
return ;
}
if (val<V[now])
Erase(L[now],val);
else
Erase(R[now],val);
update(now);
maintain(now);
}
int Find(int &now,int val)
{
assert(now);
if (val==V[now])
{
down(now);
return now;
}
down(now);
if (val<V[now])
return Find(L[now],val);
else
return Find(R[now],val);
}
void Scan(int now)
{
if (!now)return ;
Scan(L[now]);
printf("%d[%d] ",V[now],mkv[now]);
Scan(R[now]);
}
}SBT;
bool is_root(int now)
{
return !tpt[now].pnt || (tpt[tpt[now].pnt].ch[]!=now && tpt[tpt[now].pnt].ch[]!=now);
}
void update(int now)
{
tpt[now].cmx=max(tpt[now].val,max(tpt[tpt[now].ch[]].cmx,tpt[tpt[now].ch[]].cmx));
tpt[now].cmn=min(tpt[now].val,min(tpt[tpt[now].ch[]].cmn,tpt[tpt[now].ch[]].cmn));
tpt[now].csum=tpt[now].val+tpt[tpt[now].ch[]].csum+tpt[tpt[now].ch[]].csum; tpt[now].smx=max(SBT.vmx[tpt[now].sroot],
max(tpt[tpt[now].ch[]].smx,tpt[tpt[now].ch[]].smx));
tpt[now].smn=min(SBT.vmn[tpt[now].sroot],
min(tpt[tpt[now].ch[]].smn,tpt[tpt[now].ch[]].smn));
tpt[now].ssum=SBT.sum[tpt[now].sroot]+
tpt[tpt[now].ch[]].ssum+tpt[tpt[now].ch[]].ssum; tpt[now].siz=SBT.siz[tpt[now].sroot]+tpt[tpt[now].ch[]].siz+tpt[tpt[now].ch[]].siz;
tpt[now].dsiz=+tpt[tpt[now].ch[]].dsiz+tpt[tpt[now].ch[]].dsiz;
}
void make_reverse(int now)
{
tpt[now].rev^=;
swap(tpt[now].ch[],tpt[now].ch[]);
}
void make_tree(int now,int v)
{
tpt[now].smake=v;
tpt[now].splus=;
//printf("Make Tree:%d %d\n",now,v);
if (tpt[now].siz)
{
if (tpt[now].sroot)SBT.Tree_make(tpt[now].sroot,v);
tpt[now].smx=tpt[now].smn=v;
tpt[now].ssum=v*tpt[now].siz;
}
}
void make_splus(int now,int v)
{
tpt[now].splus+=v;
tpt[now].ssum+=v*tpt[now].siz;
tpt[now].smx+=v;
tpt[now].smn+=v;
if (tpt[now].sroot)
SBT.Tree_plus(tpt[now].sroot,v);
}
void make_chain(int now,int v)
{
tpt[now].val=v;
tpt[now].cmake=v;
tpt[now].cplus=;
tpt[now].cmx=tpt[now].cmn=v;
tpt[now].csum=v*tpt[now].dsiz;
}
void make_cplus(int now,int v)
{
tpt[now].val+=v;
tpt[now].cplus+=v;
tpt[now].cmx+=v;
tpt[now].cmn+=v;
tpt[now].csum+=v*tpt[now].dsiz;
} void down(int now)
{
if (tpt[now].rev)
{
if (tpt[now].ch[])make_reverse(tpt[now].ch[]);
if (tpt[now].ch[])make_reverse(tpt[now].ch[]);
tpt[now].rev=;
}
if (tpt[now].smake!=INF)
{
if (tpt[now].ch[])make_tree(tpt[now].ch[],tpt[now].smake);
if (tpt[now].ch[])make_tree(tpt[now].ch[],tpt[now].smake);
tpt[now].smake=INF;
}
if (tpt[now].splus)
{
if (tpt[now].ch[])make_splus(tpt[now].ch[],tpt[now].splus);
if (tpt[now].ch[])make_splus(tpt[now].ch[],tpt[now].splus);
tpt[now].splus=;
}
if (tpt[now].cmake!=INF)
{
Plog("TPT DOWN:%d\n",now);
if (tpt[now].ch[])make_chain(tpt[now].ch[],tpt[now].cmake);
if (tpt[now].ch[])make_chain(tpt[now].ch[],tpt[now].cmake);
tpt[now].cmake=INF;
}
if (tpt[now].cplus)
{
if (tpt[now].ch[])make_cplus(tpt[now].ch[],tpt[now].cplus);
if (tpt[now].ch[])make_cplus(tpt[now].ch[],tpt[now].cplus);
tpt[now].cplus=;
}
}
void rotate(int now)
{
int p=tpt[now].pnt,anc=tpt[p].pnt;
int dir=tpt[p].ch[]==now;
if (!is_root(p))
tpt[anc].ch[tpt[anc].ch[]==p]=now;
tpt[now].pnt=anc;
tpt[tpt[now].ch[dir]].pnt=p;
tpt[p].ch[-dir]=tpt[now].ch[dir];
tpt[p].pnt=now;
tpt[now].ch[dir]=p;
update(p);
update(now);
} int get_prv(int now)
{
int x=now;
stack[++tops]=x;
while (!is_root(x))
{
x=tpt[x].pnt;
stack[++tops]=x;
}
while (~tops)down(stack[tops--]);
if (tpt[now].ch[])
{
now=tpt[now].ch[];
down(now);
while (now && tpt[now].ch[])
{
now=tpt[now].ch[];
down(now);
}
return now;
}else
{
while (now && tpt[tpt[now].pnt].ch[]==now)
now=tpt[now].pnt;
now=tpt[now].pnt;
return now;
}
}
void splay(int now)
{
int x=now;
stack[++tops]=x;
while (!is_root(x))
{
x=tpt[x].pnt;
stack[++tops]=x;
if (x==troot)troot=now;
}
if (tpt[x].pnt)
{
int p=tpt[x].pnt;
SBT.Erase(tpt[p].sroot,x);
}
while (~tops)
down(stack[tops--]);
while (!is_root(now))
{
int p=tpt[now].pnt;
int anc=tpt[p].pnt;
if (is_root(p))
rotate(now);
else if ((tpt[anc].ch[] == p) == (tpt[p].ch[] == now))
rotate(p),rotate(now);
else
rotate(now),rotate(now);
}
if (tpt[now].pnt)
{
int p=tpt[now].pnt;
SBT.Insert(tpt[p].sroot,now,p);
}
}
int access(int now)
{
int x=now;
while (x)
{
stack[++tops]=x;
x=tpt[x].pnt;
}
while (~tops)
{
down(stack[tops]);
if (tops && is_root(stack[tops-]))
SBT.Find(tpt[stack[tops]].sroot,stack[tops-]);
tops--;
}
int son=;
while (now)
{
splay(now);
if (son)SBT.Erase(tpt[now].sroot,son);
if (tpt[now].ch[])SBT.Insert(tpt[now].sroot,tpt[now].ch[],now);
tpt[now].ch[]=son;
update(now);
son=now;
now=tpt[now].pnt;
}
return son;
}
void make_root(int now)
{
troot=now;
make_reverse(access(now));
}
void link(int x,int y)
{
make_root(x);
access(x);
make_root(y);
access(y);
tpt[x].pnt=y;
tpt[y].ch[]=x;
update(y);
}
void tree_make(int now,int val)
{
access(now);
int t=get_prv(now);
if (t)splay(t);
make_tree(now,val);
make_chain(now,val);
if (t)update(t);
}
void chain_make(int x,int y,int val)
{
make_root(x);
make_chain(access(y),val);
}
void tree_plus(int now,int val)
{
access(now);
splay(now);
int t=get_prv(now);
if (t)splay(t);
make_splus(now,val);
make_cplus(now,val);
if (t)update(t);
}
void chain_plus(int x,int y,int val)
{
make_root(x);
make_cplus(access(y),val);
}
int chain_sum(int x,int y)
{
make_root(x);
return tpt[access(y)].csum;
}
int chain_max(int x,int y)
{
make_root(x);
return tpt[access(y)].cmx;
}
int chain_min(int x,int y)
{
make_root(x);
return tpt[access(y)].cmn;
}
int tree_sum(int x)
{
access(x);
int t=get_prv(x);
if (t)splay(t);
return tpt[x].ssum+tpt[x].csum;
}
int tree_max(int x)
{
access(x);
int t=get_prv(x);
if (t)splay(t);
return max(tpt[x].cmx,tpt[x].smx);
}
int tree_min(int x)
{
access(x);
int t=get_prv(x);
if (t)splay(t);
return min(tpt[x].cmn,tpt[x].smn);
}
bool same_tree(int x,int y)
{
while (tpt[x].pnt)x=tpt[x].pnt;
while (tpt[y].pnt)y=tpt[y].pnt;
return x==y;
}
void Scan_chain(int now)
{
if (!now)return ;
down(now);
Scan_chain(tpt[now].ch[]);
printf("%d ",now);
Scan_chain(tpt[now].ch[]);
}
int edge[MAXN][];
void Print()
{
printf("-------------------------\n");
for (int j=;j<=n;j++)
{
printf("Node #%d#\n",j);
if (tpt[j].smake==)printf("Taged\n");
if (!is_root(j))continue;
printf("Root :%d\n",j);
printf("TreeA:\n");
Scan_chain(j);
printf("\n");
printf("TreeB:\n");
SBT.Scan(tpt[j].sroot);
printf("\n");
printf("\n");
}
printf("\n");
}
int main()
{
freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int croot;
scanf("%d%d",&n,&m);
tpt[].cmx=tpt[].smx=-INF;
tpt[].cmn=tpt[].smn=INF;
int x,y,z;
for (int i=;i<n;i++)
{
scanf("%d%d",&x,&y);
edge[i][]=x;
edge[i][]=y;
}
for (int i=;i<=n;i++)
{
scanf("%d",&x);
tpt[i].val=x;
update(i);
}
for (int i=;i<n;i++)
link(edge[i][],edge[i][]);
scanf("%d",&croot);
int opt;
int cnt=;
for (int i=;i<m;i++)
{
scanf("%d",&opt);
if (opt==)
{
scanf("%d%d",&x,&y);
make_root(croot);
tree_make(x,y);
}else if (opt==)
{
scanf("%d",&croot);
}else if (opt==)
{
scanf("%d%d%d",&x,&y,&z);
chain_make(x,y,z);
}else if (opt==)
{
scanf("%d",&x);
make_root(croot);
cnt++;
printf("%d\n",tree_min(x));
}else if (opt==)
{
scanf("%d",&x);
make_root(croot);
cnt++;
printf("%d\n",tree_max(x));
}else if (opt==)
{
scanf("%d%d",&x,&y);
make_root(croot);
tree_plus(x,y);
}else if (opt==)
{
scanf("%d%d%d",&x,&y,&z);
chain_plus(x,y,z);
}else if (opt==)
{
scanf("%d%d",&x,&y);
cnt++;
printf("%d\n",chain_min(x,y));
}else if (opt==)
{
scanf("%d%d",&x,&y);
cnt++;
printf("%d\n",chain_max(x,y));
}else if (opt==)
{
scanf("%d%d",&x,&y);
if (croot==x)continue;
make_root(croot);
access(x);
z=get_prv(x);
if (z)
{
splay(z);
assert(tpt[x].pnt==z);
assert(tpt[z].ch[]==x);
tpt[z].ch[]=;
tpt[x].pnt=;
update(z);
}
if (same_tree(x,y))
{
link(x,z);
}else
{
link(x,y);
}
}else if (opt==)
{
scanf("%d %d",&x,&y);
cnt++;
printf("%d\n",chain_sum(x,y));
}else if (opt==)
{
scanf("%d",&x);
make_root(croot);
cnt++;
printf("%d\n",tree_sum(x));
}
// Print();
}
return ;
}