C. DFS Trees

C. DFS Trees

https://codeforces.ml/contest/1707/problem/C

题意

\(findMST(i)\) 代表从点i开始，按照一下算法，生成的生成树(不一定是最小生成树)。
问i取1~n，findMST(i)是否是最小生成树 输出01串，0代表不行 1代表行。边权按边的顺序从1-n赋值。

思路

首先确定一点，最小生成树是唯一确定的，因为每条边都不相同。
如果一条边（u,v）不是最小生成数上的一边，那么从u到v的路径上的所有点的子树上的点都不可能生成最小生成树(处u, v外)。

具体做法：
1.用prime算法(其他也行)找到那颗最小生成树
2.记录路径(u, v) 树上差分
如果u v(假设u比v深)的lca(u, v) == v 那么就让u的价值-1 v的在路径上的儿子的价值+1
如果lca(u, v) 是两个点外的一个的 那么该lca的价值+1 u v的价值都-1
最后跑一个dfs 每次父亲的价值加给儿子 如果当前节点的价值不为零就代表这个点出发不能生成最小生成树。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const ll N = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 998244353;
int n, m, vis[N], fa[N], ans[N], val[N];
vector<int>g[N];
vector<pair<int, pair<int, int>>>e;

ll f[N][32], is[N], dep[N];

void dfs(ll x, ll pre, ll d)//找到每个节点父亲与深度
{
	f[x][0] = pre;
	dep[x] = d;
	for (auto to : g[x])
		if (to != pre)
			dfs(to, x, d + 1);
}

pair<ll, ll> lca(ll u, ll v)
{
	if (dep[u] > dep[v])
		swap(u, v);
	ll temp = dep[v] - dep[u] - 1;
	for (ll i = 0; ((1ll << i) <= temp); i++)//将u v移到同一深度
	{
		if ((1ll << i) & temp) {
			v = f[v][i];
		}
	}
	if (u == f[v][0]) return { v, f[v][0] };
	v = f[v][0];
	for (ll i = log2(n); i >= 0; i--)//两个节点一起往上走
	{								 //最多合法的跳跃是 2 ^ log2(n)
		if (f[u][i] != f[v][i])//如果相同则代表跳的太多了
		{
			u = f[u][i];
			v = f[v][i];
		}
	}
	return { u, f[u][0] };
}

void init()
{
	dfs(1, -1, 0);
	for (ll j = 0; (1ll << j) <= n; j++)//预处理出每个节点往上走2^j所到的节点，超过根节点记为-1
	{
		for (ll i = 1; i <= n; i++)
		{
			if (f[i][j] < 0)
				f[i][j + 1] = -1;
			else
				f[i][j + 1] = f[f[i][j]][j];
		}
	}
}

int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void getmst() {
	for (auto x : e) {
		int u = x.second.first;
		int v = x.second.second;
		int w = x.first;

		u = find(u);
		v = find(v);
		if (u != v) {
			fa[u] = v;
			vis[w] = 1;
		}
	}
}

void dfs2(int x, int fa) {
	ans[x] = 1;
	if (val[x]) ans[x] = 0;
	for (auto to : g[x]) {
		if (to == fa) continue;
		val[to] += val[x];
		dfs2(to, x);
	}
}

void solve()
{
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		e.push_back({ i, {u, v} });
	}

	for (int i = 1; i <= n; i++) fa[i] = i;
	sort(e.begin(), e.end());
	getmst();

	
	int root = 1;
	for (auto x : e) {
		int u = x.second.first;
		int v = x.second.second;
		int w = x.first;
		if (vis[w]){
			g[u].push_back(v);
			g[v].push_back(u);
		}
	}

    init();
	for (auto x : e) {
		int u = x.second.first;
		int v = x.second.second;
		int w = x.first;
		if (!vis[w]) {
			auto [lc1, lc2] = lca(u, v);
			if (lc2 == u || lc2 == v) {
				if (dep[u] > dep[v]) swap(u, v);
				val[v]--;
				val[lc1]++;
			}
			else {
				val[u]--;
				val[v]--;
				val[1]++;
			}
		}
	}

	dfs2(1, -1);

	for (int i = 1; i <= n; i++)
		cout << ans[i];
	cout << "\n";
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int _t = 1;
	//cin >> _t;
	while (_t--)
		solve();
	return 0;
}

原文地址：http://www.cnblogs.com/yaqu-qxyq/p/16875128.html