专栏文章

题解：P11967 [GESP202503 八级] 割裂

wwwt100127
P11967题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipqwe6j
此快照首次捕获于
2025/12/03 16:28
3 个月前
此快照最后确认于
2025/12/03 16:28
3 个月前
查看原文

题意

给定一颗树，几对好点 {⟨u1,v1⟩,⟨u2,v2⟩,…,⟨ua,va⟩}\{\langle u_1, v_1 \rangle, \langle u_2, v_2 \rangle, \dots, \langle u_a, v_a \rangle\} 和一个坏点对 ⟨bu,bv⟩\langle b_u, b_v \rangle。⟨ui,vi⟩\langle u_i, v_i \rangle 之间的点不能，只能选 ⟨bu,bv⟩\langle b_u, b_v \rangle 之间的点，求有几个点可以被选择。

思路

以 bub_u 为根，则只能选从 bvb_v 到根上的路径，用一个 bool 数组记录（不妨在 bub_u 到 bvb_v 的路径上的为 truetrue）。
定义 fif_i 表示共有多少组 ⟨ui,vi⟩\langle u_i, v_i \rangle 的路径经过点 ii。
对于每一组 ⟨ui,vi⟩\langle u_i, v_i \rangle，树上差分即可。
具体来说，就是：
CPP
  f[u[i]]++;
  f[v[i]]++;
  f[LCA(u[i],v[i])]--;
  f[father[LCA(u[i],v[i])]]--;
然后对于每一组父子关系 (fa,x)(fa,x)，f[fa]+=f[x] 即可。
点 pp 不在任意一组 ⟨ui,vi⟩\langle u_i, v_i \rangle 所在路径上，当且仅当 fp=0f_p=0。
综上所述，一个点 ii 可以被选择，当且仅当 ansi=trueans_i = true 并且 fi=0f_i=0。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

namespace Memory_Love{
	int read(){ int x=0; bool flag=1; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
	template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
	template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
	template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
		static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
		while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
	int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
	int lcm(int a,int b){return a/gcd(a,b)*b;}
	int lowbit(int x){return (x&-x);}
} using namespace Memory_Love;
const int N=1e6+5;
int n,m,s,t;

namespace Graph
{
	int head[N],tot;
	struct edge
	{
		int v,next;
	}e[N<<1];
	void G_init()
	{
		memset(head,-1,sizeof(head));
		tot=-1;
	}
	void add(int u,int v)
	{
		e[++tot]=(edge){v,head[u]};
		head[u]=tot;
	}
	void add_edge(int u,int v)
	{
		add(u,v),add(v,u);
	}
} using namespace Graph;

vector<PII> G;

namespace SP
{
	int dfn[N],rev[N],cnt;
	int depth[N],father[N];
	int son[N],top[N],SIZE[N];
	void dfs1(int x,int fa)
	{
		int i;
		SIZE[x]=1;
		father[x]=fa;
		depth[x]=depth[fa]+1;
		for(i=head[x];~i;i=e[i].next)
		{
			int y=e[i].v;
			if(y==fa)
			continue;
			dfs1(y,x);
			SIZE[x]+=SIZE[y];
			if(SIZE[y]>SIZE[son[x]])
			son[x]=y;
		}
	}
	void dfs2(int x,int topx)
	{
		int i;
		dfn[x]=++cnt;
		rev[cnt]=x;
		top[x]=topx;
		if(son[x]) dfs2(son[x],topx);
		for(i=head[x];~i;i=e[i].next)
		{
			int y=e[i].v;
			if(!top[y])
			dfs2(y,y);
		}
	}
	void init(int root)
	{
		dfs1(root,0);
		dfs2(root,root);
	}
	int LCA(int x,int y)
	{
		while(top[x]!=top[y])
		{
			if(depth[top[x]]<depth[top[y]])
			swap(x,y);
			x=father[top[x]];
		}
		return (depth[x]<depth[y]? x:y);
	}
}

int f[N];
bool ans[N];
void dfs(int x,int fa)
{
	int i;
	if(x==t) ans[x]=1;
	for(i=head[x];~i;i=e[i].next)
	{
		int y=e[i].v;
		if(y==fa)
		continue;
		dfs(y,x);
		ans[x]|=ans[y];
		f[x]+=f[y];
	}
}

bool Ending;
signed main()
{
	int i,u,v,Ans=0;
	read(n,m);
	G_init();
	for(i=1;i<=n-1;i++)
	{
		read(u,v);
		add_edge(u,v);
	}
	for(i=1;i<=m;i++)
	{
		read(u,v);
		G.push_back(mp(min(u,v),max(u,v)));
	}
	read(s,t);
	SP::init(s);
	
	for(auto t:G)
	{
		int lca=SP::LCA(t.fi,t.se);
		f[t.fi]++,f[t.se]++;
		f[lca]--,f[SP::father[lca]]--;
	}
	dfs(s,0);
	for(i=1;i<=n;i++)
	{
		if(ans[i] && f[i]==0)
		Ans++;
	}
	write(Ans,'\n');
	
	cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...