点的距离（模板题）

树中两点间的距离就是d[u] + d[v] - 2 * d[lca(u, v)]

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 1e5 + 10;

const int MAXM = 20;

struct Edge { int to, next; };

Edge e[MAXN << 1];

int head[MAXN], num, n;

int up[MAXN][MAXM + 10], d[MAXN];

void AddEdge(int from, int to)

{

	e[num] = Edge{to, head[from]};

	head[from] = num++;

}

void dfs(int u, int fa)

{

	for(int i = head[u]; ~i; i = e[i].next)

	{

		int v = e[i].to;

		if(v == fa) continue;

		d[v] = d[u] + 1;

		up[v][0] = u;

		dfs(v, u);

	}

}

void get_up()

{

	_for(j, 1, MAXM)

		_for(i, 1, n)

			up[i][j] = up[up[i][j-1]][j-1];

}

int lca(int u, int v)

{

	if(d[u] < d[v]) swap(u, v);

	for(int i = MAXM; i >= 0; i--)

		if(d[up[u][i]] >= d[v])

			u = up[u][i];

	if(u == v) return u;

	for(int i = MAXM; i >= 0; i--)

		if(up[u][i] != up[v][i])

			u = up[u][i], v = up[v][i];

	return up[u][0];

}

int main()

{

	memset(head, -1, sizeof(head));

	num = 0; scanf("%d", &n);

	REP(i, 1, n)

	{

		int u, v;

		scanf("%d%d", &u, &v);

		AddEdge(u, v); AddEdge(v, u);

	}

	dfs(1, -1);

	get_up();

	int q; scanf("%d", &q);

	while(q--)

	{

		int u, v;

		scanf("%d%d", &u, &v);

		printf("%d\n", d[u] + d[v] - 2 * d[lca(u, v)]);

	}

	return 0;

}

暗的连锁

这道题首先有个转化

切两刀能不能切断，取决于非树边，因为非树边会构成环

那么可以把非树边构成的环上所有的树边都覆盖一次

如果只覆盖一次，那么显然有唯一解

如果没有被覆盖，那就加上非树边的数目，因为第二刀可以切任意一条非树边

如果覆盖两次以上，那么两刀是不能解决问题的。

所以就有维护每条边被覆盖了多少次

这里用到了树上差分，f[u]表示u与u的父亲连的边的覆盖次数

对于非树边u, v，让f[u]++, f[v]++, f[lca(u, v)]--

最后在“前缀和回来”，即统计所有子树的值加起来，就是答案

最后注意计算答案的时候根的f数组不算，因为根没有父亲

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 1e5 + 10;

const int MAXM = 20;

struct Edge{ int to, next; };

Edge e[MAXN << 1];

int head[MAXN], num, n, m;

int up[MAXN][MAXM + 10], d[MAXN];

int f[MAXN];

void read(int& x)

{

	int f = 1; x = 0; char ch = getchar();

	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }

	while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }

	x *= f;

}

void AddEdge(int to, int from)

{

	e[num] = Edge{to, head[from]};

	head[from] = num++;

}

void dfs(int u, int fa)

{

	for(int i = head[u]; ~i; i = e[i].next)

	{

		int v = e[i].to;

		if(v == fa) continue;

		d[v] = d[u] + 1;

		up[v][0] = u;

		dfs(v, u);

	}

}

int dp(int u, int fa)

{

	for(int i = head[u]; ~i; i = e[i].next)

	{

		int v = e[i].to;

		if(v == fa) continue;

		dp(v, u);

		f[u] += f[v];

	}

}

void init()

{

	dfs(1, -1);

	_for(j, 1, MAXM)

		_for(i, 1, n)

			up[i][j] = up[up[i][j - 1]][j - 1];

}

int lca(int u, int v)

{

	if(d[u] < d[v]) swap(u, v);

	for(int i = MAXM; i >= 0; i--)

		if(d[up[u][i]] >= d[v])

			u = up[u][i];

	if(u == v) return u;

	for(int i = MAXM; i >= 0; i--)

		if(up[u][i] != up[v][i])

			u = up[u][i], v = up[v][i];

	return up[u][0];

}

int main()

{

	read(n);read(m);

	memset(head, -1, sizeof(head)); num = 0;

	REP(i, 1, n)

	{

		int u, v; read(u), read(v);

		AddEdge(u, v); AddEdge(v, u);

	}

	init();

	_for(i, 1, m)

	{

		int u, v; read(u), read(v);

		f[u]++; f[v]++; f[lca(u, v)] -= 2;

	}

	dp(1, -1);

	int ans = 0;

	_for(i, 2, n)

	{

		if(f[i] == 1) ans++;

		if(f[i] == 0) ans += m;

	}

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

	return 0;

}

巴特西

LCA题集

点的距离（模板题）

暗的连锁

最新文章

热门文章