C++ 解法, 执行用时: 2074ms, 内存消耗: 16644K, 提交时间: 2022-02-18 22:03:50
//ayanami保佑，夸哥保佑，狗妈保佑，MDR保佑，锉刀怪保佑，M99保佑，克爹保佑
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int p1=1000000,p2=0;
char buf[1000005],wb[1000005];
int gc() {
if(p1>=1000000)fread(buf,1,1000000,stdin),p1=0;
return buf[p1++];
}
//#define gc getchar
#define Loli true
#define Kon xor true
long long getint() {
long long ret=0,flag=1;
char c=gc();
while(c<'0'||c>'9') {
if(c=='-')flag=-1;
c=gc();
}
while(c<='9'&&c>='0') {
ret=(ret<<3)+(ret<<1)+c-'0';
c=gc();
}
return ret*flag;
}
void pc(char x) {
if(p2>=1000000)fwrite(wb,1,1000000,stdout),p2=0;
wb[p2++]=x;
}
void wrt(long long x) {
if(x<0)pc('-'),x=-x;
int c[24]= {0};
if(!x)return pc('0'),void();
while(x)c[++c[0]]=x%10,x/=10;
while(c[0])pc(c[c[0]--]+'0');
}
const int inf = 0x3f3f3f3f;
int n,m;
int max(int a,int b,int c){return max(a,max(b,c));}
void ins(int d[2],int val){if(val>d[0])d[1]=d[0],d[0]=val;else d[1]=max(d[1],val);}
void ins(int d[2],int val[2]){ins(d,val[0]),ins(d,val[1]);}
namespace T{
int tot,sta[100005];
struct node{
int ch[3],fa,col,pre,suf,prec,sufc,sum,rev,ctag,ans[2],val[2][2];
node(){ch[0]=ch[1]=ch[2]=0,fa=col=0,pre=suf=prec=sufc=0,sum=0,rev=ctag=0,ans[0]=ans[1]=-inf,val[0][0]=val[1][1]=val[0][1]=val[1][0]=-inf;}
}v[200005];
void push_rev(int x){if(!x)return;v[x].rev^=1,swap(v[x].pre,v[x].suf),swap(v[x].prec,v[x].sufc),swap(v[x].ch[0],v[x].ch[1]),swap(v[x].val[0][0],v[x].val[0][1]),swap(v[x].val[1][0],v[x].val[1][1]);}
void push_ctag(int x){if(!x)return;v[x].ctag^=1,v[x].prec^=1,v[x].sufc^=1,v[x].col^=1,swap(v[x].val[0][0],v[x].val[1][0]),swap(v[x].val[0][1],v[x].val[1][1]),swap(v[x].ans[0],v[x].ans[1]);}
void push_up(int x){
if(!x)return;
bool bj=x>n;
if(!bj){
v[x].pre=v[x].ch[0]?(v[x].prec=v[v[x].ch[0]].prec,v[v[x].ch[0]].pre):(v[x].prec=v[x].col,x);
v[x].suf=v[x].ch[1]?(v[x].sufc=v[v[x].ch[1]].sufc,v[v[x].ch[1]].suf):(v[x].sufc=v[x].col,x);
int ls=v[x].ch[0]&&v[v[x].ch[0]].sufc!=v[x].col,rs=v[x].ch[1]&&v[v[x].ch[1]].prec!=v[x].col;
int mxs[2]={v[v[x].ch[2]].val[v[x].col][0],v[v[x].ch[2]].val[v[x].col][1]};
int mxd[2]={v[v[x].ch[2]].val[!v[x].col][0],v[v[x].ch[2]].val[!v[x].col][1]};
v[x].sum=v[v[x].ch[0]].sum+ls+rs+v[v[x].ch[1]].sum;
v[x].val[0][0]=max(v[v[x].ch[0]].val[0][0],v[v[x].ch[0]].sum+ls+max(max(mxs[0],v[x].col?0:-inf),mxd[0]+1),v[v[x].ch[0]].sum+ls+rs+v[v[x].ch[1]].val[0][0]);
v[x].val[0][1]=max(v[v[x].ch[1]].val[0][1],v[v[x].ch[1]].sum+rs+max(max(mxs[0],v[x].col?0:-inf),mxd[0]+1),v[v[x].ch[1]].sum+rs+ls+v[v[x].ch[0]].val[0][1]);
v[x].val[1][0]=max(v[v[x].ch[0]].val[1][0],v[v[x].ch[0]].sum+ls+max(mxs[0]+1,max(mxd[0],!v[x].col?0:-inf)),v[v[x].ch[0]].sum+ls+rs+v[v[x].ch[1]].val[1][0]);
v[x].val[1][1]=max(v[v[x].ch[1]].val[1][1],v[v[x].ch[1]].sum+rs+max(mxs[0]+1,max(mxd[0],!v[x].col?0:-inf)),v[v[x].ch[1]].sum+rs+ls+v[v[x].ch[0]].val[1][1]);
v[x].ans[0]=max(v[v[x].ch[0]].ans[0],v[v[x].ch[1]].ans[0],v[v[x].ch[2]].ans[0]);
v[x].ans[1]=max(v[v[x].ch[0]].ans[1],v[v[x].ch[1]].ans[1],v[v[x].ch[2]].ans[0]);
int tmp[2]={-inf,-inf};
ins(tmp,v[v[x].ch[0]].val[0][1]+ls),ins(tmp,v[v[x].ch[1]].val[0][0]+rs),ins(tmp,max(mxs[0],v[x].col?0:-inf)),ins(tmp,max(mxs[1],v[x].col?0:-inf)),ins(tmp,mxd[0]+1),ins(tmp,mxd[1]+1),v[x].ans[0]=max(v[x].ans[0],(tmp[0]>0?0:-inf),tmp[0]+tmp[1]),tmp[0]=tmp[1]=-inf;
ins(tmp,v[v[x].ch[0]].val[1][1]+ls),ins(tmp,v[v[x].ch[1]].val[1][0]+rs),ins(tmp,mxs[0]+1),ins(tmp,mxs[1]+1),ins(tmp,max(mxd[0],!v[x].col?0:-inf)),ins(tmp,max(mxd[1],!v[x].col?0:-inf)),v[x].ans[1]=max(v[x].ans[1],(tmp[0]>0?0:-inf),tmp[0]+tmp[1]),tmp[0]=tmp[1]=-inf;
}else{
v[x].ans[0]=max(v[v[x].ch[0]].ans[0],v[v[x].ch[1]].ans[0],v[v[x].ch[2]].ans[0]);
v[x].val[0][0]=v[x].val[0][1]=v[x].val[1][0]=v[x].val[1][1]=-inf;
ins(v[x].val[0],v[v[x].ch[0]].val[0]),ins(v[x].val[0],v[v[x].ch[1]].val[0]);
ins(v[x].val[1],v[v[x].ch[0]].val[1]),ins(v[x].val[1],v[v[x].ch[1]].val[1]);
ins(v[x].val[v[v[x].ch[2]].prec],v[v[x].ch[2]].val[0][0]);
}
}
void push_down(int x){
if(v[x].rev)push_rev(v[x].ch[0]),push_rev(v[x].ch[1]),v[x].rev=0;
if(v[x].ctag)push_ctag(v[x].ch[0]),push_ctag(v[x].ch[1]),v[x].ctag=0;
}
void add_son(int x,int t,int y) {v[x].ch[t]=y,v[y].fa=x;}
bool isroot(int x){return x!=v[v[x].fa].ch[0]&&x!=v[v[x].fa].ch[1];}
void rot(int x){
int p=v[x].fa,g=v[p].fa,d=(v[p].ch[1]==x);
if(g)v[g].ch[v[g].ch[2]==p?2:(v[g].ch[1]==p)]=x;
v[x].fa=g,add_son(p,d,v[x].ch[!d]),add_son(x,!d,p);
push_up(p);
}
void pre_push_down(int x){
if(!isroot(x))pre_push_down(v[x].fa);
push_down(x);
}
void splay(int x){
pre_push_down(x);
while(!isroot(x)){
int p=v[x].fa,g=v[p].fa;
if(!isroot(p))rot((v[g].ch[0]==p)^(v[p].ch[0]==x)?x:p);
rot(x);
}
push_up(x);
}
void erase(int x){v[sta[++sta[0]]=x]=node();}
int new_node(){return sta[0]?sta[sta[0]--]:++tot;}
void local_splay(int x,int d) {
int goal=v[x].fa;
while(v[x].ch[d])x=v[x].ch[d];
while(!isroot(x)&&v[x].fa!=goal)rot(x);
}
void splice(int x){
splay(x),x=v[x].fa,splay(x);
int y=v[x].ch[2];
if(v[x].ch[1])swap(v[v[x].ch[1]].fa,v[v[y].ch[2]].fa),swap(v[x].ch[1],v[y].ch[2]);
else{
add_son(x,1,v[y].ch[2]);
if(v[y].ch[0])local_splay(v[y].ch[0],1),add_son(v[y].ch[0],1,v[y].ch[1]),v[x].ch[2]=v[y].ch[0];
else v[x].ch[2]=v[y].ch[1];
erase(y),y=v[x].ch[2],v[y].fa=x;
}
push_up(y),push_up(x),rot(v[x].ch[1]);
}
void access(int x) {
if(x==0)exit(0);
splay(x);
if(v[x].ch[1]) {
int y=new_node();
add_son(y,0,v[x].ch[2]),add_son(y,2,v[x].ch[1]);
push_up(y),v[x].ch[1]=0,add_son(x,2,y),push_up(x);
}
while(v[x].fa)splice(v[x].fa),push_up(x);
}
void makeroot(int x){access(x),splay(x),push_rev(x);}
void link(int x,int y){access(x),makeroot(y),v[y].fa=x,v[x].ch[1]=y,push_up(x);}
void cut(int x,int y){makeroot(x),access(y),splay(y),v[v[y].ch[0]].fa=0,v[y].ch[0]=0,push_up(y);}
void expose(int x,int y){makeroot(x),access(y),splay(y);}
}
int main() {
n=getint(),m=getint(),T::tot=n;
for(int i=1;i<n;i++)T::link(getint(),getint());
for(int i=1;i<=n;i++)if(getint())T::makeroot(i),T::access(i),T::push_ctag(i);
for(int i=1;i<=m;i++){
int a=getint(),b=getint(),c=getint(),d=getint(),e=getint();
T::cut(c,a),T::link(a,b),T::expose(d,e),T::push_ctag(e),T::access(1),T::splay(1),wrt(T::v[1].ans[0]<0?0:T::v[1].ans[0]/2+1),pc('\n');
}
fwrite(wb,1,p2,stdout);
return Loli Kon;
}
，给定每个点的颜色黑或者白。表示树点数和操作次数。
接下来行每行两个数表示一条树边。
接下来一行个数，其中每个数都是 0 或 1。
若第个数为 0，则第
行每行 5 个数
表示在
为根的意义下将
的父亲换为
，之后翻转链
的颜色。