题意

给一棵N个节点的树，编号从1到N，再给定m对点(u，v),你要将树上的每条无向边变为有向边，使得给定的点对都满足u能到达v或v能到达u。问有多少种不同的方案，答案对(1e9+7)求余。

1 ≤ ​N, m≤ 3e5

题解

我们先推一下

若两个点（U，V）中间有这么一条有向路，那么，路径会不会包括 lca（U，V）上面的点呢？

众所周知，这是树，每个点到祖先只有一条路径，一种走法，若上的去，就下不来了，所以答案是否定的。

于是这道题就要用求lca的方法。

在这条有向路径中所有的边肯定都是一个方向吧，那么说来，就是被一条路径涵盖的边，相当于都处于一个集合中，只要其中之一的方向确定，其他边便都推的出来，整个集合就固定只有两种不同的方案了。这个可以用并查集实现。

怎么确定并查集解法呢。

如果lca(u,v)到u是一种方向（两种方向分别是指向根结点或叶子结点），那么lca(u,v)到v肯定是另一种方向（不同于lca(u,v)到u）。也就是说，lca(u,v)到u的路径的一种方向的情况是与lca(u,v)到v的路径的另一种方向的情况相联系（属于同一种情况中，好好揣摩揣摩），简单来说就是要合并集合。

一个更难的问题，怎么确定方向呢？

干脆，不确定方向了，把两种方向的有向边都建立起来！

这样就好办了，向上的边连向上的边，向下的边连向下的边，lca(u,v)到u的向上边集合就和lca(u,v)到v的向下集合合并……

合并到最后，如果，同一条边向上向下的两种情况都在同一个集合中，这意味着什么？——这条边向上可以推出这条边向下，肯定不对啊！这时意味着无解，就直接输出零了。

从上面的推理可以看出，一条向上或向下的路径（边都处于同一种方向）的处理方式都是相同的。因此我们只需要知道哪些边需要处理，向上合并还是向下合并就行，合并左右路径的不同方向直接在u，v两点向上连的边提前合并。

因此，输入每对（u，v）后，在u点和v点标记要向上处理的深度，最后用一遍dfs连边就行。

对于如何计算那个深度，我是老老实实打倍增算的，巨佬们有好方法自己用。

最后的答案等于 2 ^(并查集集合数 / 2),自己思考。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<vector>

#include<stack>

#include<queue>

#include<cmath>

#include<map>

#define max(x,y) ((x) > (y) ? (x) : (y))

#define min(x,y) ((x) < (y) ? (x) : (y))

#define abs(x) ((x) < 0 ? -(x) : (x))

#define LL long long

#define lowbit(x) (-(x) & (x))

using namespace std;

int read() {

	int f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}

	while(s >= '0' && s <= '9') {x = x * 10 + s - '0';s = getchar();}

	return x * f;

}

struct it{

	int v,id;

	it(){}

	it(int V,int I){v = V;id = I;}

};

LL mod = 1e9 + 7;

LL ans = 1;

int n,m,i,j,s,o,k,cnt;

int l[300005],r[300005];

vector<it> g[300005];

int d[300005];

int fa[600005];

int fat[300005][20];

int fi[300005];

bool vis[600005];

int q[300005];

int find(int x) {//推荐用循环，不用递归

	while(x != fa[x]) {

		x = fa[x] = fa[fa[x]];

	}

	return fa[x];

}

void unionSet(int a,int b) {

	int u = find(a),v = find(b);

	if(u > v)fa[u] = v;

	if(u < v)fa[v] = u;

	return ;

}

void pdfs(int x) {

	vis[x] = 1;

	d[x] = d[fat[x][0]] + 1;

	for(int i = 1;i <= 19;i ++) {

		fat[x][i] = fat[fat[x][i - 1]][i - 1];

	}

	for(int i = 0;i < g[x].size();i ++) {

		if(!vis[g[x][i].v]) {

			fat[g[x][i].v][0] = x;

			fi[g[x][i].v] = g[x][i].id;

			pdfs(g[x][i].v);

		}

	}

	return ;

}

int LCA(int a,int b) {

	if(d[a] > d[b]) {

		for(int i = 19;i >= 0;i --) {

			if(d[fat[a][i]] >= d[b]) a = fat[a][i];

		}

	}

	if(d[a] < d[b]) {

		for(int i = 19;i >= 0;i --) {

			if(d[fat[b][i]] >= d[a]) b = fat[b][i];

		}

	}

	if(a == b) return a;

	for(int i = 19;i >= 0;i --) {

		if(fat[a][i] != fat[b][i]) {

			a = fat[a][i];

			b = fat[b][i];

		}

	}

	return fat[a][0];

}

int dfs(int x,int pe) {

	vis[x] = 1;

	int de = 0x7f7f7f7f;

	for(int i = 0;i < g[x].size();i ++) {

		if(g[x][i].v != fat[x][0] && !vis[g[x][i].v]) {

			int dde = dfs(g[x][i].v,g[x][i].id);

			de = min(de,dde);

			if(d[x] > dde) {

				unionSet(pe,g[x][i].id);

				unionSet(pe + n,g[x][i].id + n);

			}

			de = min(de,dde);

			de = min(de,dde);

			de = min(de,dde);

			de = min(de,dde);

		}

	}

	de = min(de,q[x]);

	return de;

}

int main() {

	n = read();m = read();

	for(int i = 1;i < n;i ++) {

		s = read();o = read();

		g[s].push_back(it(o,i));

		g[o].push_back(it(s,i));

		fa[i] = i;fa[n + i] = n + i;

	}

	fat[1][0] = 1;

	pdfs(1);

	memset(q,0x3f,sizeof(q));

	for(int i = 1;i <= m;i ++) {

		l[i] = read();r[i] = read();

		int lca = LCA(l[i],r[i]);

		q[l[i]] = min(q[l[i]],d[lca]);

		q[r[i]] = min(q[r[i]],d[lca]);

		if(lca != l[i] && lca != r[i]) {

			unionSet(fi[l[i]],fi[r[i]] + n);

			unionSet(fi[l[i]] + n,fi[r[i]]);

		}

	}

	memset(vis,0,sizeof(vis));

	dfs(1,0);

	bool flag = 1;

	for(int i = 1;i < n;i ++) {

		if(find(i) == find(i + n)) {

			flag = 0;

		}

	}

	if(!flag) {

		printf("0\n");

		return 0;

	}

	memset(vis,0,sizeof(vis));

	int ce = 0;

	for(int i = 1;i < n;i ++) {

		if(!vis[find(i)]) {

			vis[find(i)] = 1;

			ce ++;

		}

	}

	for(int i = n + 1;i < n + n;i ++) {

		if(!vis[find(i)]) {

			vis[find(i)] = 1;

			ce ++;

		}

	}

	ce /= 2;

	for(int i = 1;i <= ce;i ++) {

		ans = ans * 2 % mod;

	}

	printf("%lld\n",ans);

	return 0;

}

数月之后的下一篇：Codeforces Round #585 (Div. 2) E. Marbles （状压DP），BZOJ大理石（同一道题）题解

Usmjeri(COCI2017.2)题解的相关教程结束。