A 构造题
考虑枚举答案 
，则所有数都是 的倍数或 的倍数 
，预处理出每个数的出现次数，然后枚举倍数可以做到 )
的复杂度，其中 
是值域。
注意最终的答案可能
。
注意最终的答案可能
#include<cstdio>
#define re //register
using namespace std;
char rbuf[20000002];
int pt=-1;
inline int read(){
re int t=0;re char v=rbuf[++pt];
while(v<'0')v=rbuf[++pt];
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=rbuf[++pt];
return t;
}
inline int max(re int x,re int y){return x>y?x:y;}
int v[1000002],mx,n;
int main(){
fread(rbuf,1,20000000,stdin),n=read();
for(re int i=1,x;i<=n;++i)mx=max(mx,x=read()),++v[x];
++mx;
for(re int i=mx;i;--i){
re int s=0;
for(re int j=i;j<=mx;j+=i)s+=v[j]+v[j-1];
if(s==n)return printf("%d",i),0;
}
} B 异或矩阵
结论，令 
为最大的满足 
的数，答案可以取到 
。
构造：
若
与 
相邻，则一定可以选这两个数。
否则，令 在第 
行，则 在第 
行，此时 
一定为奇数，取这两行中间的两个数即可。
构造：
若
否则，令
#include<cstdio>
#define int long long
#define re //register
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int n,m,k,X1,Y1,X2,Y2;
inline void Pos(re int x,re int &a,re int &b){
a=(x-1)/m+1;
b=x-a*m+m;
}
signed main(){
n=read(),m=read();
if(n==1&&m==1){
puts("1\n1 1 1 1");
return 0;
}
k=1;
while(k*2<=n*m)k<<=1;
Pos(k-1,X1,Y1),Pos(k,X2,Y2);
printf("%lld\n",k+k-1);
if(m%2==0||X1==X2)printf("%lld %lld %lld %lld",X1,Y1,X2,Y2);
else printf("%lld %lld %lld %lld\n",X1,m+1>>1,X2,m+1>>1);
} C 树上行走
将贡献化为两种：来自父亲的和来自儿子的，来自父亲的相当于链操作，很好维护，来自儿子的可以分为轻儿子和重儿子，可以在重链剖分的时候处理，以上的链操作均可用简单的树状数组完成，时间复杂度 )
。
#include<cstdio>
#define re //register
#define ll long long
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int n,m,top[1000002],head[1000002],cnt,c1[1000002],dfn[1000002],a[1000002],son[1000002],fa[1000002],dep[1000002],siz[1000002],c2[1000002],tim;
ll b[1000002];
inline void addd(re int *c,re int x,re int y){
while((x<=n||y<=n)&&(x^y)){
if(x<y)++c[x],x+=x&(-x);
else --c[y],y+=y&(-y);
}
}
inline void del(re int *c,re int x){for(;x<=n;x+=x&(-x))--c[x];}
inline int ask(re int *c,re int x,re int s=0){for(;x;x^=x&(-x))s+=c[x];return s;}
struct edge{int to,next;}e[2000002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
inline void dfs1(re int x,re int y){
dep[x]=dep[y]+1,fa[x]=y,siz[x]=1;
for(re int i=head[x];i;i=e[i].next)
if(e[i].to^y){
dfs1(e[i].to,x),siz[x]+=siz[e[i].to];
if(siz[e[i].to]>siz[son[x]])son[x]=e[i].to;
}
}
inline void dfs2(re int x,re int y){
top[x]=y,dfn[x]=++tim;
if(son[x])dfs2(son[x],y);
for(re int i=head[x];i;i=e[i].next)
if(e[i].to^fa[x]&&e[i].to^son[x])
dfs2(e[i].to,e[i].to);
}
inline int lca(re int x,re int y){
while(top[x]^top[y]){
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
int main(){
n=read(),m=read();
for(re int i=1;i<=n;++i)a[i]=read();
for(re int i=1,x,y;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
dfs1(1,1);dfs2(1,1);
while(m--){
re int o=read();
if(o==1){
re int x=read(),y=read(),z=lca(x,y);
addd(c2,dfn[y],dfn[z]);
while(top[x]^top[z]){
addd(c1,dfn[top[x]],dfn[x]);
b[fa[top[x]]]+=a[top[x]],x=fa[top[x]];
}
addd(c1,dfn[z],dfn[x]);
}
else{
re int x=read();
printf("%lld\n",b[x]+1ll*ask(c1,dfn[x])*a[son[x]]+1ll*(ask(c2,dfn[x]+siz[x]-1)-ask(c2,dfn[x]-1))*a[fa[x]]);
}
}
} D 树上博弈
如果加上初始的限制，以及链长可能是奇数，可以发现，若先手无法走到对称点，后手一定可以走到先手走到的点的对称点，那么此时先手必败。
回到树上，在树上与链拥有相似性质的是直径（由于每次距离是严格大于上一次可以直接看成一条长度为直径的链，每个点在链上的位置相当于到直径中点的距离），于是问题就转化为了判断到直径中点的距离，新增点可以倍增维护，暴力求出新直径即可，时间复杂度
#include<bits/stdc++.h>
#define re //register
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int n,m,head[600002],cnt,fa[22][600002],L[600002],dep[600002],p1,p2,D;
struct edge{int to,next;}e[1200002];
inline void add(re int x,re int y){e[++cnt]=(edge){y,head[x]},head[x]=cnt;}
inline void dfs(re int x,re int y){
fa[0][x]=y,dep[x]=dep[y]+1;
for(re int i=1;i<=19;++i)fa[i][x]=fa[i-1][fa[i-1][x]];
for(re int i=head[x];i;i=e[i].next)
if(e[i].to^y)
dfs(e[i].to,x);
}
inline int lca(re int x,re int y){
if(dep[x]<dep[y])swap(x,y);
for(re int i=19;~i;--i)if(dep[fa[i][x]]>=dep[y])x=fa[i][x];
if(x==y)return x;
for(re int i=19;~i;--i)if(fa[i][x]^fa[i][y])x=fa[i][x],y=fa[i][y];
return fa[0][x];
}
inline int dis(re int x,re int y){return dep[x]+dep[y]-dep[lca(x,y)]*2;}
inline void Ins(re int x){
int tmp;
if((tmp=dis(p1,x))>D)p2=x,D=tmp;
if((tmp=dis(p2,x))>D)p1=x,D=tmp;
}
inline int kth(re int x,re int y){
for(re int i=19;~i;--i)if(y&(1<<i))x=fa[i][x];
return x;
}
int main(){
n=read(),m=read();
for(re int i=1,x,y;i<n;++i)x=read(),y=read(),add(x,y),add(y,x);
dfs(1,1),p1=1,p2=2,D=dis(1,2);
for(re int i=3;i<=n;++i)Ins(i);
while(m--){
re int o=read(),x=read();
if(o==1){
++n,fa[0][n]=x,dep[n]=dep[x]+1;
for(re int i=1;i<=19;++i)fa[i][n]=fa[i-1][fa[i-1][n]];
Ins(n);
}
else{
re int y=read();
if(n==1){
puts("0");
continue;
}
if(dep[p1]<dep[p2])swap(p2,p1);
if(D&1){
re int pos=kth(p1,D>>1);
puts(min(dis(y,pos),dis(y,fa[0][pos]))*2+1>x?"1":"0");
}
else{
re int pos=kth(p1,D>>1);
puts(dis(y,pos)*2>x?"1":"0");
}
}
}
}
E 集合划分
假设我们知道了两个集合的 
分别为 
，假设 
，
单独讨论，这里是容易的，那么我们发现此时的数有五类，
，每一种数都有不同的贡献。
令
表示 
且 
为 较大的一边时所有数的方案数，令 
表示 且 为 较小的一边时 
的方案数相对 
的变化量（也就是说在 中，我们要求这些数在大的一边出现，此时要求在两边都出现，也就是从 
变为了 
）此时 
恰好表示了一边 为 另一边为 
时的答案。
对于额外的要求
，我们用一次分治 NTT 来解决，时间复杂度 )
。
令
对于额外的要求
#include<bits/stdc++.h>
#define re //register
using namespace std;
inline int read(){
re int t=0;re char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
namespace Poly{
const int M=998244353;
inline int ksm(re int x,re int y){
re int s=1;
while(y){
if(y&1)s=1ll*s*x%M;
x=1ll*x*x%M,y>>=1;
}
return s;
}
inline void add(re int &x,re int y){(x+=y)>=M?x-=M:x;}
inline int Mod(re int x){return x>=M?x-M:x;}
inline void Out(vector<int>A){
puts("\n--------");
printf("%d\n",A.size());
for(re int i=0;i<A.size();++i)printf("%d ",A[i]);
puts("");
puts("--------\n");
}
int N,W[2097152],rev[2097152],wi[2097152];
inline void pre(re int n){
re int wn=ksm(3,(M-1)/n);N=n;
for(re int i=W[0]=1;i<n;++i)W[i]=1ll*W[i-1]*wn%M;
}
inline int make(re int n){
re int l=ceil(log2(n));n=1<<l;
for(re int i=0;i<n;++i)rev[i]=rev[i>>1]>>1|((i&1)<<(l-1));
return n;
}
inline void NTT(vector<int>&A,re int n,re int f){
for(re int i=0;i<n;++i)if(i<rev[i])swap(A[i],A[rev[i]]);
for(re int i=1;i<n;i<<=1){
for(re int j=0;j<i;++j)wi[j]=W[f==1?j*(N/(i<<1)):(j?(N-j*(N/(i<<1))):j)];
for(re int j=0;j<n;j+=i<<1)
for(re int k=j;k<j+i;++k){
re int x=A[k],y=1ll*A[k+i]*wi[k-j]%M;
add(A[k],y),A[k+i]=Mod(x-y+M);
}
}
if(f==-1){
re int iv=ksm(n,M-2);
for(re int i=0;i<n;++i)A[i]=1ll*A[i]*iv%M;
}
}
inline void mul(vector<int>A,vector<int>B,vector<int>&C){
re int k=make(A.size()+B.size()-1),o=A.size()+B.size()-1;
A.resize(k),B.resize(k),C.resize(k);
NTT(A,k,1),NTT(B,k,1);
for(re int i=0;i<k;++i)C[i]=1ll*A[i]*B[i]%M;
NTT(C,k,-1),C.resize(o);
}
}
using namespace Poly;
int n,m,a[200002],k,F[200002],G[200002],ANS[400002];
inline void solve(re int l,re int r){
if(l==r)return;
re int mid=l+r>>1;
solve(l,mid),solve(mid+1,r);
vector<int>L,R,Ans;
for(re int i=l;i<=mid;++i)L.push_back(G[i]);
for(re int i=mid+1;i<=r;++i)R.push_back(F[i]);
mul(L,R,Ans);
for(re int i=l+mid+1;i<=mid+r;++i)add(ANS[i],Ans[i-l-mid-1]);
}
int main(){
srand(time(0));
n=read(),k=read(),pre(262144);
for(re int i=0;i<=n;++i){
a[i]=read();
F[i]=ksm(2,a[i])-1,G[i]=ksm(2,a[i])-2;
if(i)F[i]=1ll*F[i-1]*F[i]%M,G[i]=1ll*G[i-1]*G[i]%M;
if(a[i]==0)G[i]=0;
else G[i]=1ll*G[i]*ksm(ksm(2,a[i])-1,M-2)%M;
if(G[i]<0)G[i]+=M;
}
for(re int i=n+1;i;--i)F[i]=F[i-1],G[i]=G[i-1];
F[0]=G[0]=1,++n;
re int s=1;
for(re int i=n;~i;--i)G[i]=1ll*G[i]*ksm(ksm(2,a[i])-1,M-2)%M,F[i]=1ll*F[i]*s%M,s=1ll*s*ksm(2,a[i])%M;
solve(0,n),s=1;
for(re int i=0;i<=n;++i)s=1ll*s*ksm(2,a[i])%M;
for(re int i=0;i<=n+n;++i)add(ANS[i],ANS[i]);
for(re int i=0;i<=n;++i){
s=1ll*s*ksm(ksm(2,a[i]),M-2)%M;
if(a[i]==0)add(ANS[i+i],s);
if(a[i]<=1)break;
s=1ll*s*(ksm(2,a[i])-2)%M;
}
for(re int i=0;i<=k;++i)printf("%d ",ANS[i]);
}
F Laplace
结论一：一条链上翻转次数至少为黑色节点的段数。
- proof. 第一种方法：每次把一段黑色节点翻了即可。第二种方法：每次找到最左和最右的黑点，翻转这两个节点间的连通块即可。
结论二：一颗树上的最少翻转次数为找到一条链，使得黑色节点的段数最大，段数就是翻转的次数。
- proof. 考虑引理一的这个答案一定是整棵树答案的下界，证明其一定取到即可。方法：每次选择极大的、每个叶子节点都是黑点的连通点集，翻转整个点集，可以取到下界。
结论三：我们定义一条树边，如果他链接的两个端点为同色则边权为 0，如果为异色则边权为 1，则一条链上黑色段数等于链上距离最远的黑色点对的距离除以 2 加 1。
- proof. 一段黑色节点必定对应两个异色边，再加上两边是黑色端点，故上述距离计算方式等于黑色段数，等于最小翻转次数。
所以问题转化为了边权为 0 或者 1 的树上直径问题，每次暴力 DFS 得到平方算法。考虑加速优化即为用 LCT 对树形结构以及边权进行维护。LCT 维护动态直径就直接在每个节点计算跨越当前节点，并且两端点在子结构以内的所有链即可。
考虑到树链 reverse，树链 flip 均无法快速计算维护，因此我们直接预先维护其做了操作之后的答案，懒标记打上的时候直接 swap 即可。
Q：思路和程序正确，也是用的标解的方法，为什么我的程序超时了？（通过率在 90% 左右）
A：可能为评测机波动，或者你的程序常数较大。
目前能够通过的方法：LCT 维护直径，查询的时候相当于查询子树最大值。
目前因为常数大被卡的方法：LCT 维护直径，查询时 makeroot 距离最远点，得到直径的一个端点作为根，查得直径。
这道题明确定位是没有卡双 log 的。
Q：为什么标程奇快无比？
A：因为他比你少一个 log。
- proof. 第一种方法：每次把一段黑色节点翻了即可。第二种方法：每次找到最左和最右的黑点，翻转这两个节点间的连通块即可。
结论二：一颗树上的最少翻转次数为找到一条链，使得黑色节点的段数最大，段数就是翻转的次数。
- proof. 考虑引理一的这个答案一定是整棵树答案的下界，证明其一定取到即可。方法：每次选择极大的、每个叶子节点都是黑点的连通点集，翻转整个点集，可以取到下界。
结论三：我们定义一条树边，如果他链接的两个端点为同色则边权为 0，如果为异色则边权为 1，则一条链上黑色段数等于链上距离最远的黑色点对的距离除以 2 加 1。
- proof. 一段黑色节点必定对应两个异色边，再加上两边是黑色端点，故上述距离计算方式等于黑色段数，等于最小翻转次数。
所以问题转化为了边权为 0 或者 1 的树上直径问题，每次暴力 DFS 得到平方算法。考虑加速优化即为用 LCT 对树形结构以及边权进行维护。LCT 维护动态直径就直接在每个节点计算跨越当前节点，并且两端点在子结构以内的所有链即可。
考虑到树链 reverse，树链 flip 均无法快速计算维护，因此我们直接预先维护其做了操作之后的答案，懒标记打上的时候直接 swap 即可。
Q：思路和程序正确，也是用的标解的方法，为什么我的程序超时了？（通过率在 90% 左右）
A：可能为评测机波动，或者你的程序常数较大。
目前能够通过的方法：LCT 维护直径，查询的时候相当于查询子树最大值。
目前因为常数大被卡的方法：LCT 维护直径，查询时 makeroot 距离最远点，得到直径的一个端点作为根，查得直径。
这道题明确定位是没有卡双 log 的。
Q：为什么标程奇快无比？
A：因为他比你少一个 log。
//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;
}
全部评论
(2) 回帖