膜膜膜,常数挺小的。。。

 #include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
#define rep(i,a,n) for(int i=a;i<n;i++)
using namespace std;
const int maxn=1e5+,inf=-1u>>;
int getint(){
int res=,f=;char c=getchar();
while(!isdigit(c))f=f==-||c=='-'?-:,c=getchar();
while(isdigit(c))res=res*+c-'',c=getchar();
return res*f;
}
int n,m;
struct info{
int mx,mn,sum,siz;
info(){}
info(int mx,int mn,int sum,int siz):
mx(mx),mn(mn),sum(sum),siz(siz){}
};
struct flag{
int mul,add;
flag(){mul=;}
flag(int mul,int add):
mul(mul),add(add){}
bool empty(){return mul==&&add==;}
};
info operator+(const info &a,const flag &b) {
return a.siz?info(a.mx*b.mul+b.add,a.mn*b.mul+b.add,a.sum*b.mul+b.add*a.siz,a.siz):a;
}
info operator+(const info &a,const info &b) {
return info(max(a.mx,b.mx),min(a.mn,b.mn),a.sum+b.sum,a.siz+b.siz);
}
flag operator+(const flag &a,const flag &b) {
return flag(a.mul*b.mul,a.add*b.mul+b.add);
}
struct node{
node *ch[],*f;
flag Cha,All;
info cha,sub,all;
bool rev,inr;
int val;
void revt(){rev^=;swap(ch[],ch[]);}
void makec(const flag &a){
Cha=Cha+a;cha=cha+a;val=val*a.mul+a.add;
all=cha+sub;
}
void makes(const flag &a,bool _=){
All=All+a;all=all+a;sub=sub+a;
if(_)makec(a);
}
void update(){
cha=all=sub=info(-inf,inf,,);
if(!inr)all=cha=info(val,val,val,);
rep(i,,)if(ch[i])cha=cha+ch[i]->cha,sub=sub+ch[i]->sub;
rep(i,,)if(ch[i])all=all+ch[i]->all;
rep(i,,)if(ch[i])sub=sub+ch[i]->all;
}
void down(){
if(rev){
if(ch[])ch[]->revt();
if(ch[])ch[]->revt();
rev=;
}
if(!All.empty()){
rep(i,,)if(ch[i])ch[i]->makes(All,i>=);
All=flag(,);
}
if(!Cha.empty()){
rep(i,,)if(ch[i])ch[i]->makec(Cha);
Cha=flag(,);
}
}
node *C(int i){if(ch[i])ch[i]->down();return ch[i];}
bool d(int ty){return f->ch[ty+]==this;}
int D(){rep(i,,)if(f->ch[i]==this)return i;}
void sets(node *x,int d){if(x)x->f=this;ch[d]=x;}
bool rt(int ty){
if(ty==)return !f||(f->ch[]!=this&&f->ch[]!=this);
else return !f||!f->inr||!inr;
}
}nd[maxn*],*cur=nd+maxn,*pool[maxn],**Cur=pool;
int _cnt;
node *newnode(){
_cnt++;
node *x=(Cur==pool)?cur++:*(--Cur);
rep(i,,)x->ch[i]=;x->f=;
x->All=x->Cha=flag(,);
x->all=x->cha=info(-inf,inf,,);
x->inr=;x->rev=;x->val=;
return x;
}
void dele(node *x){*(Cur++)=x;}
void rot(node *x,int ty){
node *p=x->f;int d=x->d(ty);
if(!p->f)x->f=;else p->f->sets(x,p->D());
p->sets(x->ch[!d+ty],d+ty);x->sets(p,!d+ty);p->update();
}
void splay(node *x,int ty=){
while(!x->rt(ty)){
if(x->f->rt(ty))rot(x,ty);
else if(x->d(ty)==x->f->d(ty))rot(x->f,ty),rot(x,ty);
else rot(x,ty),rot(x,ty);
}x->update();
}
void add(node *u,node *w){
w->down();
rep(i,,)if(!w->ch[i]){w->sets(u,i);return;}
node *x=newnode(),*v;
for(v=w;v->ch[]->inr;v=v->C());
x->sets(v->ch[],);x->sets(u,);
v->sets(x,);splay(x,);
}
void del(node *w){
if(w->f->inr){
w->f->f->sets(w->f->ch[-w->D()],w->f->D());
dele(w->f);splay(w->f->f,);
}else w->f->sets(,w->D());
w->f=;
}
void access(node *w){
static node *sta[maxn];
static int top=;
node *v=w,*u;
for(u=w;u;u=u->f)sta[top++]=u;
while(top)sta[--top]->down();
splay(w);
if(w->ch[])u=w->ch[],w->ch[]=,add(u,w),w->update();
while(w->f){
for(u=w->f;u->inr;u=u->f);
splay(u);
if(u->ch[])w->f->sets(u->ch[],w->D()),splay(w->f,);
else del(w);
u->sets(w,);
(w=u)->update();
}splay(v);
}
void makert(node *x){
access(x);x->revt();
}
node *findp(node *u){
access(u);u=u->C();
while(u&&u->ch[])u=u->C();
return u;
}
node *findr(node *u){for(;u->f;u=u->f);return u;}
node* cut(node *u){
node *v=findp(u);
if(v)access(v),del(u),v->update();
return v;
}
void link(node *u,node *v) {
node* p=cut(u);
if(findr(u)!=findr(v))p=v;
if(p)access(p),add(u,p),p->update();
}
int main(){
n=getint();m=getint();
static int _u[maxn],_v[maxn];
rep(i,,n)_u[i]=getint(),_v[i]=getint();
rep(i,,n+){
nd[i].val=getint();
nd[i].update();
}
rep(i,,n)makert(nd+_u[i]),link(nd+_u[i],nd+_v[i]);
int root=getint();
makert(nd+root);
int x,y,z;
node *u,*v;
while(m--){
int k=getint();x=getint();
u=nd+x;
if(k==||k==||k==||k==||k==){
access(u);
if(k==||k==||k==){
int ans=u->val;
rep(i,,)if(u->ch[i]){
info res=u->ch[i]->all;
if(k==) ans=min(ans,res.mn);
else if(k==) ans=max(ans,res.mx);
else if(k==) ans+=res.sum;
}printf("%d\n",ans);
}else{
y=getint();
flag fg(k==,y);
u->val=u->val*fg.mul+fg.add;
rep(i,,)if(u->ch[i])u->ch[i]->makes(fg);
u->update();
}
}else if(k==||k==||k==||k==||k==){
y=getint();
makert(u),access(nd+y),splay(u);
if (k==||k==||k==) {
info ans=u->cha;
if (k==) printf("%d\n",ans.mn);
else if (k==) printf("%d\n",ans.mx);
else printf("%d\n",ans.sum);
}else u->makec(flag(k==,getint()));
makert(nd+root);
}else if(k==)link(u,nd+getint());
else if(k==)makert(u),root=x;
}
return ;
}
05-02 10:50