自动搬运

查看原文

来自洛谷，原作者为

	maojun 猫君

搬运于2025-08-24 22:00:08，当前版本为作者最后更新于2023-12-28 16:28:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一种小常数单 $\log$ 做法。

把 $1$ 定为树根，那么对于每条边，要么是指向父亲（$0$），要么是指向儿子（$1$）。

考虑转换 $m$ 条限制：$u\rightarrow lca,v\rightarrow lca$ 的路径上的边分别全 $0$、全 $1$ 或分别全 $1$ 全 $0$。

我们记一个点 $u$ （$1<u\le n$）的点权表示指向 $u$ 的边的状态（$0/1$），则可以得到两条限制（$son_u$ 表示 $lca$ 往 $u$ 跳一步走到的点，$son_v$ 同理）：

1. $u,son_u$ 路径上的点权相同

2. $v,son_v$ 路径上的点权相同

3. $u,v$ 的点权不同（注意若 $lca$ 为 $u$ 或 $v$，则没有这条限制）

那么对于限制 $1,2$，每次合并树上的一条祖先链，连通块内相同。

对于考虑限制 $3$，若 $u,v$ 已经在一个联通块，则矛盾，输出 $0$；否则连接 $u,v$ 所在的联通块。

把连通块缩点，得到一个无向图，则有解必须满足该图可以黑白染色。那直接建出来然后 dfs 一遍就好了。若有解则答案即为 $2$ 的新图的连通块数量次方，因为若联通的点确定，则可以确定；否则不会被确定。

后面的两个操作用并查集复杂度 $O(n\alpha(n))$，问题就是合并一条树链。

考虑给链上除了顶点的点打上一个标记，若一个点超过一个标记，则将它和它的父亲合并。树上差分 + 并查集即可，复杂度 $O(n\alpha(n))$。

于是瓶颈在求 lca，精细实现可以优化到 $O(n)$。我写的是树剖 lca，总复杂度 $O(n\log n)$。

常数非常小，加上快读可以直接拿到（目前的）最优解。

const int N=3e5+5,MOD=1e9+7;
int n,m,u[N],v[N];
const int E=N<<1;
int tot=0,head[N],to[E],nxt[E];
inline void Add(int u,int v){to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}

int f[N];									// 并查集
inline void init(){for(int i=1;i<=n;i++)f[i]=i;}
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline void merge(int u,int v){u=find(u);v=find(v);if(u^v)f[u]=v;}

int fa[N],dep[N],siz[N],son[N],top[N];		// 树剖
void dfs1(int u,int fath){
	fa[u]=fath;dep[u]=dep[fath]+1;siz[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fath)continue;
		dfs1(v,u);siz[u]+=siz[v];(siz[v]>siz[son[u]])&&(son[u]=v);
	}
}
void dfs2(int u,int tp){
	top[u]=tp;if(!son[u])return;dfs2(son[u],tp);
	for(int i=head[u];i;i=nxt[i]){int v=to[i];if(v^son[u]&&v^fa[u])dfs2(v,v);}
}
inline int LCA(int u,int v){for(;top[u]^top[v];u=fa[top[u]])if(dep[top[u]]<dep[top[v]])swap(u,v);return dep[u]<dep[v]?u:v;}
inline int gson(int u,int v){
	int lst=0;
	for(;top[v]^top[u];v=fa[top[v]])lst=top[v];
	return u==v?lst:son[u];
}

bool vis[N],col[N];
void dfs(int u){							// 黑白染色
	vis[u]=true;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(vis[v]){if(col[u]==col[v]){puts("0");exit(0);};continue;}
		col[v]=!col[u];dfs(v);
	}
}
bool fl[N];int d[N];
void dfs(int u,int fath){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];if(v==fath)continue;
		dfs(v,u);d[u]+=d[v];
	}
	if(d[u])merge(fath,u);					// 若有标记则合并
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;i++){scanf("%d%d",&u,&v);Add(u,v);Add(v,u);}
	dfs1(1,0);dfs2(1,1);init();
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u[i],&v[i]);
		int l=LCA(u[i],v[i]);
		if(u[i]^l){d[u[i]]++;d[gson(l,u[i])]--;}
		if(v[i]^l){d[v[i]]++;d[gson(l,v[i])]--;}
		if(u[i]==l||v[i]==l){fl[i]=true;continue;}// 注意特判 lca=u 或 lca=v 的情况
	}
	dfs(1,0);
	tot=0;memset(head,0,sizeof head);
	for(int i=1;i<=m;i++){
		u[i]=find(u[i]);v[i]=find(v[i]);
		if(fl[i])continue;
		if(u[i]^v[i]){Add(u[i],v[i]);Add(v[i],u[i]);}
		else{puts("0");return 0;}			// 若有 u,v 不同的限制，u,v 却在一个块内
	}
	int res=1;
	for(int i=2;i<=n;i++)if(f[i]==i&&!vis[i]){
		dfs(i);res=(res<<1)%MOD;			// 找到一个联通块，答案乘2
	}
	printf("%d\n",res);
	return 0;
}