联合省选2021 D1T3与D2T1

我写一下我考场上的做法吧，也算是退役前留下的最后一点点东西了。

听说D2T1有\(O(n)\)做法，orz

D1T3

首先容易发现，对于一张图\(G\)，对\(f(u,G)\)有贡献的\(\{v\}\)，是存在一条从\(u\)到\(v\)的路径上的点均不小于\(v\)，且存在一条从\(v\)到\(u\)的路径上的点均不小于\(v\)。

以上对应于原图与反图，保留不小于\(v\)的点后，\(v\)均能走到的点数。

总共有\(O(m)\)张图，对于每个\(v\)，可以\(O(m)\)求一遍，这样暴力的复杂度为\(O(m^2n)\)，我考场上写的这个暴力对拍跑大样例是\(0.4s\sim 0.5s\)的（\(n=100,m=1000\)），估计能拿\(44\)分

对于每张图，是没必要都求一遍的：
枚举点\(v\)，可以动态加入边（从最后一条边加起），当走过一个点后，就把这个点的出边全删掉，记录每个点最早能被\(v\)遍历到的时间。

这样是\(O(nm+n^2)\)的，具体可以看看我下面的代码

#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
#define opt operator
#define pii std::pair<LL,LL>
const LL maxn=2e5+9,mod=998244353,G=3;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<‘0‘ || c>‘9‘){
		if(c==‘-‘) f=-1; c=getchar();
	}
	while(c>=‘0‘ && c<=‘9‘){
		x=(x<<3ll)+(x<<1ll)+c-‘0‘; c=getchar();
	}
	return x*f;
}
void Chkmax(LL &x,LL y){
	x=y>x?y:x;
}
void Chkmin(LL &x,LL y){
	x=y<x?y:x;
}
LL add(LL x,LL y){
	x+=y;
	return x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
	x-=y;
	return x<0?x+mod:x;
}
LL mul(LL x,LL y){
	return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
	LL ret(1);
	while(b){
		if(b&1) ret=mul(ret,base);
		base=mul(base,base); b>>=1;
	}
	return ret;
}
struct Edge{
	LL x,y;
}e[maxn];
LL n,m;
namespace sub2{
	LL mark1[maxn],mark2[maxn];
	std::vector<LL> V1[maxn],V2[maxn],Q[maxn];
	void Bfs1(LL s,LL ti){
		std::queue<LL> que; que.push(s);
		mark1[s]=ti;
		while(que.size()){
			LL u(que.front()); que.pop();
			for(LL i=0;i<V1[u].size();++i){
				LL v(V1[u][i]); if(mark1[v]) continue;
				mark1[v]=ti;
				que.push(v); //mark1[v]=1;
			}
			std::vector<LL>().swap(V1[u]);
		}
	}
	void Bfs2(LL s,LL ti){
		std::queue<LL> que; que.push(s);
		mark2[s]=ti;
		while(que.size()){
			LL u(que.front()); que.pop();
			for(LL i=0;i<V2[u].size();++i){
				LL v(V2[u][i]); if(mark2[v]) continue;
				mark2[v]=ti;
				que.push(v); //mark1[v]=1;
			}
			std::vector<LL>().swap(V2[u]);
		}
	}
	void Solve(){
		static LL cf[maxn];
		for(LL i=1;i<=n;++i){
			for(LL j=1;j<=n;++j) mark1[j]=mark2[j]=0;
			for(LL j=1;j<=n;++j){
				std::vector<LL>().swap(V1[j]);
				std::vector<LL>().swap(V2[j]);
			}
			mark1[i]=m+1;
			mark2[i]=m+1;
			for(LL j=m;j>=1;--j){
				LL x(e[j].x),y(e[j].y);
				if(x>=i && y>=i){
					if(mark1[x] && !mark1[y]){
						Bfs1(y,j);
					}else if(!mark1[x] && !mark1[y]){
						V1[x].pb(y);
					}
					std::swap(x,y);
					if(mark2[x] && !mark2[y]){
						Bfs2(y,j);
					}else if(!mark2[x] && !mark2[y]){
						V2[x].pb(y);
					}
				}
			}
			for(LL j=i+1;j<=n;++j) if(mark1[j] && mark2[j]){
				LL z(std::min(mark1[j],mark2[j]));
				cf[z-1]++;
			}
		}
		for(LL i=m;i>=0;--i) cf[i]+=cf[i+1];
		for(LL i=0;i<=m;++i) printf("%d ",cf[i]+n); puts("");
	}
}
int main(){
	//if(system("diff x.txt "))
	//return 0;
//	freopen("graph.in","r",stdin);
//	freopen("graph.out","w",stdout);
	double ret1(clock());
	n=Read(); m=Read();
	for(LL i=1;i<=m;++i){
		LL x(Read()),y(Read());
		e[i]=(Edge){x,y};
	}
	sub2::Solve();
	return 0;
	//printf("%.10lf\n",(clock()-ret1)/CLOCKS_PER_SEC);
}

D2T1

这题关键在于，\(p_i\)均不相同，那么就说明，如果我们知道走到\(u\)这个位置并且吃掉了，那么现在的状态就已知了。

考虑链的部分分，是可以\(O(nlogn)\)倍增预处理（细节较多不说了）

再考虑树，对树重链剖分，对于\(x\)往上走到某个祖先节点的贡献，同链
对于\(x\)往下走到某个子树节点，可以在重链上走，重链上同链那样预处理，总复杂度\(O(nlogn+qlog^2n)\)

#include<bits/stdc++.h>
typedef int LL;
#define pb push_back
#define opt operator
#define pii std::pair<LL,LL>
const LL maxn=2e5+9,mod=998244353,G=3;
LL Read(){
	LL x(0),f(1); char c=getchar();
	while(c<‘0‘ || c>‘9‘){
		if(c==‘-‘) f=-1; c=getchar();
	}
	while(c>=‘0‘ && c<=‘9‘){
		x=(x<<3ll)+(x<<1ll)+c-‘0‘; c=getchar();
	}return x*f;
}
LL add(LL x,LL y){
	x+=y;
	return x>=mod?x-mod:x;
}
LL dec(LL x,LL y){
	x-=y;
	return x<0?x+mod:x;
}
LL mul(LL x,LL y){
	return 1ll*x*y%mod;
}
LL Pow(LL base,LL b){
	LL ret(1); while(b){
		if(b&1) ret=mul(ret,base);
		base=mul(base,base); b>>=1;
	}return ret;
}
LL m;
LL root[maxn];
namespace Sgt{
	LL nod;
	LL son[maxn*30][2],a[maxn*30];
	void Modify(LL &nw,LL pre,LL l,LL r,LL x,LL v){
		nw=++nod;
		son[nw][0]=son[pre][0]; son[nw][1]=son[pre][1];
		if(l==r){
			a[nw]=v; return;
		}
		LL mid(l+r>>1);
		if(x<=mid) Modify(son[nw][0],son[pre][0],l,mid,x,v);
		else Modify(son[nw][1],son[pre][1],mid+1,r,x,v);
	}
	LL Query(LL nw,LL l,LL r,LL x){
		if(l==r) return a[nw];
		LL mid(l+r>>1);
		if(x<=mid) return Query(son[nw][0],l,mid,x);
		else return Query(son[nw][1],mid+1,r,x);
	}
	LL Find(LL u,LL c){
		return Query(root[u],1,m,c);
	}
}
LL n,C,q;
LL fa[maxn],dep[maxn],p[maxn],w[maxn],pos[maxn],gf[maxn],son[maxn],top[maxn],istop[maxn];
LL size[maxn];
//gf: top first p[1]
LL lp1[maxn][20],lp2[maxn][20],dp1[maxn][20],dp2[maxn][20],inc[maxn][20];
std::vector<LL> V[maxn],col[maxn];
void Init(){
	n=Read(); m=Read(); C=Read();
	for(LL i=1;i<=C;++i){
		p[i]=Read();
	}
	for(LL i=1;i<=C;++i){
		pos[p[i]]=i;
	}
	for(LL i=1;i<=n;++i) w[i]=Read();
	for(LL i=1;i<n;++i){
		LL x(Read()),y(Read());
		V[x].pb(y); V[y].pb(x);
	}
}
void Dfs1(LL u,LL f){
	dep[u]=dep[f]+1; fa[u]=f;
	LL x(pos[w[u]]);
	if(x){
		LL y(p[x+1]);
		//printf("# %d: %d %d\n",u,x,y);
		y=(col[y].size()?col[y].back():0);
		//printf("%d\n",y);
		for(LL i=0;i<=19;++i) dp2[u][i]=dp1[y][i];
		dp1[u][0]=u;
		//dp2[u][0]=y;
		for(LL i=1;i<=19;++i){
			LL v(dp1[u][i-1]);
			dp1[u][i]=dp2[v][i-1];
		}
		//for(LL i=0;i<=3;++i) printf("%d ",dp1[u][i]); puts("");
		//for(LL i=0;i<=3;++i) printf("%d ",dp2[u][i]);
		//puts(""); puts("");
	}
	inc[u][0]=f;
	for(LL i=1;i<=19;++i){
		inc[u][i]=inc[inc[u][i-1]][i-1];
	}
	col[w[u]].pb(u);
	gf[u]=col[p[1]].size()?col[p[1]].back():0;
	size[u]=1; son[u]=0;
	for(LL i=0;i<V[u].size();++i){
		LL v(V[u][i]); if(v==f) continue;
		Dfs1(v,u); size[u]+=size[v];
		if(size[v]>size[son[u]]) son[u]=v;
	}
	col[w[u]].pop_back();
}
void Dfs2(LL u,LL f,LL ff){
	istop[son[u]]=0; top[u]=ff;
	if(son[u]){
		Dfs2(son[u],u,ff);
	}
	for(LL i=0;i<V[u].size();++i){
		LL v(V[u][i]); if(v==f || v==son[u]) continue;
		Dfs2(v,u,v);
	}
}
void Build2(){//weight lian
    Sgt::nod=0;
    for(LL i=1;i<=m;++i) std::vector<LL>().swap(col[i]);
    std::vector<LL> suq;
	for(LL tp=1;tp<=n;++tp) if(istop[tp]){
		std::vector<LL> ().swap(suq);
		LL u(tp);
		while(u){
			suq.pb(u); u=son[u];
		}
		LL sz(suq.size()-1); suq.pb(0);
		//for(LL i=sz;i>=0;--i) printf("%d ",suq[i]); puts("");
		for(LL i=sz;i>=0;--i){
			u=suq[i];
			Sgt::Modify(root[suq[i]],root[suq[i+1]],1,m,w[u],u);
		}
		for(LL i=sz;i>=0;--i){
			u=suq[i];
			LL x(pos[w[u]]);
			if(x){
				LL y(p[x+1]);
				//printf("# (%d)%d,%d\n",u,x,y);
				y=(col[y].size()?col[y].back():0);
				//printf("%d\n",y);
				for(LL j=0;j<=19;++j) lp2[u][j]=lp1[y][j];
				lp1[u][0]=u;
				for(LL j=1;j<=19;++j){
					LL v(lp1[u][j-1]);
					lp1[u][j]=lp2[v][j-1];
				}
				//for(LL j=0;j<=3;++j) printf("%d ",lp1[u][j]); puts("");
				//for(LL j=0;j<=3;++j) printf("%d ",lp2[u][j]); puts("");
			}
			col[w[u]].pb(u);
		}
        for(LL i=0;i<=sz;++i) std::vector<LL>().swap(col[w[suq[i]]]);
	}
}
void Build(){
	Dfs1(1,0);
	//puts("----------------------");
	for(LL i=1;i<=n;++i) istop[i]=1;
	Dfs2(1,0,1);
	Build2();
	//puts("-----------------------");
	/*for(LL i=1;i<=n;++i){
		Dfs3()
	}*/
}
LL Lca(LL x,LL y){
	if(dep[x]<dep[y]) std::swap(x,y);
	for(LL i=19;i>=0;--i) if(dep[inc[x][i]]>=dep[y]) x=inc[x][i];
	if(x==y) return x;
	for(LL i=19;i>=0;--i) if(inc[x][i]!=inc[y][i]){
		x=inc[x][i]; y=inc[y][i];
	}return inc[x][0];
}
pii Search1(LL x,LL y){//not in one   first:down second:son
    
	while(true){
		y=top[y];
		if(top[fa[y]]==top[x]) return pii(fa[y],y);
		y=fa[y];
	}
}
LL Search2(LL x,LL c){//x lian find c
	return Sgt::Find(x,c);
}
LL Solve(LL x,LL y){
	LL lca(Lca(x,y));
	//printf("(%d,%d)%d\n",x,y,lca);
	LL len(1);
	{
		LL u(gf[x]);
		//printf("# %d\n",u);
	    if(u){
			if(dep[u]<dep[lca]){
				x=lca;
			}else{
				x=u;
				//for(LL i=0;i<=2;++i) printf("%d ",dp2[x][i]); puts("");
				for(LL i=19;i>=0;--i) if(dep[dp2[x][i]]>=dep[lca]){
					len+=(1<<i); x=dp2[x][i];
				}
				++len; x=lca;
			}
	    }else{
		    x=lca;
	    }
	}
	if(len>C) return C;
	//printf("%d: %d,%d\n",len,x,y);
	while(top[x]!=top[y]){
		LL z(Search2(x,p[len]));
		//puts("#");
		pii tmp(Search1(x,y));
		//printf("%d (%d,%d)\n",z,tmp.first,tmp.second);
		if(!z || dep[z]>dep[tmp.first]){
			x=tmp.second;
		}else{
			x=z; //if(len>C) return C;
			for(LL i=19;i>=0;--i) if(lp2[x][i] && dep[lp2[x][i]]<=dep[tmp.first]){
				len+=(1<<i); x=lp2[x][i];
			}
			++len; x=tmp.second;
			if(len>C) return C;
		}
	}
	if(top[x]==top[y]){
		LL z(Search2(x,p[len]));
		//printf("# (%d)%d:%d\n",x,z,p[len]);
		if(!z || dep[z]>dep[y]){
			return len-1;
		}
		x=z;
		//printf("# %d\n",z);
		//for(LL i=0;i<=3;++i) printf("%d ",lp2[x][i]); puts("");
		for(LL i=19;i>=0;--i) if(lp2[x][i] && dep[lp2[x][i]]<=dep[y]){
			len+=(1<<i); x=lp2[x][i];
		}
		++len;
		assert(len<=C+1);
		return len-1;
	}
	assert(0);
}
void Solve(){
	q=Read();
	while(q--){
		LL x(Read()),y(Read());
		LL ret=Solve(x,y);
		printf("%d\n",ret);
	}
}
int main(){
	/*
	if(system("diff x.txt gem3.ans")) return 0;
	else puts("Ac");
	return 0;
//	*/
	//freopen("y1.txt","r",stdin);
//	freopen("gem.in","r",stdin);
	//double ret1(clock());
	//freopen("x.txt","w",stdout);
//	freopen("gem.out","w",stdout);
 	Init();
	//puts("-----------------");
	Build();
	//puts("-----------------");
	Solve();
	//printf("%.10lf\n",(clock()-ret1)/CLOCKS_PER_SEC);
	return 0;
}

联合省选2021 D1T3与D2T1

原文：https://www.cnblogs.com/Grice/p/14645327.html