2022-02-20 20:38 营销

关注

牛客挑战赛 57 题解

A 构造题

考虑枚举答案 $x$ ，则所有数都是 $x$ 的倍数或 $x$ 的倍数 $-1$ ，预处理出每个数的出现次数，然后枚举倍数可以做到 $O(V\log V+n)$ 的复杂度，其中 $V$ 是值域。

注意最终的答案可能 $>V$ 。

#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 异或矩阵

结论，令 $k$ 为最大的满足 $2^k\leq nm$ 的数，答案可以取到 $2^{k+1}-1$ 。

构造：

若 $2^k$ 与 $2^k-1$ 相邻，则一定可以选这两个数。

否则，令 $2^k-1$ 在第 $a$ 行，则 $2^k$ 在第 $a+1$ 行，此时 $m$ 一定为奇数，取这两行中间的两个数即可。

#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 树上行走

将贡献化为两种：来自父亲的和来自儿子的，来自父亲的相当于链操作，很好维护，来自儿子的可以分为轻儿子和重儿子，可以在重链剖分的时候处理，以上的链操作均可用简单的树状数组完成，时间复杂度 $O(n+q\log^2n)$ 。

#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 树上博弈

先考虑博弈的过程，假设博弈是在一条长度为偶数的链上进行的，且没有最初的限制，那么先手每次可以走到当前点关于链中点的对称点，可以发现此时先手一定必胜。

如果加上初始的限制，以及链长可能是奇数，可以发现，若先手无法走到对称点，后手一定可以走到先手走到的点的对称点，那么此时先手必败。

回到树上，在树上与链拥有相似性质的是直径（由于每次距离是严格大于上一次可以直接看成一条长度为直径的链，每个点在链上的位置相当于到直径中点的距离），于是问题就转化为了判断到直径中点的距离，新增点可以倍增维护，暴力求出新直径即可，时间复杂度 $O(n\log n)$ 。

#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 集合划分

假设我们知道了两个集合的 $mex$ 分别为 $x,y$ ，假设 $x<y$ ， $x=y$ 单独讨论，这里是容易的，那么我们发现此时的数有五类， $<x,=x,>x\&<y,=y,>y$ ，每一种数都有不同的贡献。

令 $g_i$ 表示 $mex=i$ 且 $i$ 为 $mex$ 较大的一边时所有数的方案数，令 $f_i$ 表示 $mex=i$ 且 $i$ 为 $mex$ 较小的一边时 $<i$ 的方案数相对 $g$ 的变化量（也就是说在 $g$ 中，我们要求这些数在大的一边出现，此时要求在两边都出现，也就是从 $2^x-1$ 变为了 $2^x-2$ ）此时 $f_ig_j$ 恰好表示了一边 $mex$ 为 $i$ 另一边为 $j$ 时的答案。

对于额外的要求 $i<j$ ，我们用一次分治 NTT 来解决，时间复杂度 $O(n\log^2 n)$ 。

#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。

//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;
}

全部评论

推荐最新楼层

Lynkcat

绍兴一中 C++

swap D E/fn/fn/fn

点赞回复分享

发布于 2022-02-22 17:58

sakuyalove

湖南大学算法工程师

E题的话我对c_i的取值范围是<=1e9有点疑惑，c_i取值范围大于998244353会不会影响取逆？因为这样2^c-1和2^c-2都可能是0（c=998244352和c=998244353）（我想用前缀积来求g_i，但是因为取逆会出问题就不知道怎么办了）(如果是c_i<=1e8我就能完全理解您的做法了 )

点赞回复分享

发布于 2022-02-22 08:12