2020牛客暑期多校训练营（第十场）

https://ac.nowcoder.com/acm/contest/5675

J - Identical Trees

题意：给定两棵树，要求修改最少的第一棵树上的节点编号，使得两棵树同构。

树上dp+费用流

$dp[u][r]$ 表示第一棵树上点 u 对应第二棵树上点 r，最少需要修改的节点数。

从两个根开始向下递归，对于所有子节点的两两对应情况都需要求，假设现在已经求出来所有子节点两两对应的结果，需要得到点 u 的结果。

需要把树1上的子节点重新排列，与树2上的子节点一一对应，结果就是各个子节点求和+根是否需要修改。

重新排列对应，使得总和最小，那么就是二分图上求费用流。

有些博客树哈希先判断两棵子树是否能对应，只连能对应的情况，其实不需要判断两棵子树是否能对应，如果不能对应，一定是在某个子节点儿子数量不同，或者两棵树儿子数量没法一一对应，只要把儿子数量不同的情况的dp值设为INF即可。费用流是在保证最大流的基础上求最小费用，所以如果没法只要合法的情况一一对应，求出的结果一定包含INF的情况，也就是无解。这也是必须用INF的原因，如果不用INF，而是不连边，则会使得本应无解的情况有结果，这结果并没有流满，是不正确的。

在稀疏图上费用流的实际效率高于KM，本题用KM可能会超时。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 510;
const ll mod = 998244353;
int n;
vector<int>G1[N], G2[N];
int dp[N][N], r1, r2;
typedef pair<int, int>pii;
struct E
{
	int from, to, cp, v;
	int rev;
	E() {}
	E(int f, int t, int cp, int v, int rev) :from(f), to(t), cp(cp), v(v), rev(rev) {}
};
struct MCMF
{
	int n, m, s, t;
	vector<E> edges;
	vector<int> G[N << 1];
	bool inq[N << 1];     //是否在队列
	int d[N << 1];        //Bellman_ford单源最短路径
	int p[N << 1];        //p[i]表从s到i的最小费用路径上的最后一条弧编号
	int a[N << 1];        //a[i]表示从s到i的最小残量
	void init(int _n, int _s, int _t) {
		n = _n; s = _s; t = _t;
		for (int i = 0; i < n; i++) G[i].clear();
		edges.clear(); m = 0;
	}

	void addedge(int from, int to, int cap, int cost) {
		edges.push_back(E(from, to, cap, cost, 0));
		edges.push_back(E(to, from, 0, -cost, 1));
		G[from].push_back(m++);
		G[to].push_back(m++);
	}

	bool BellmanFord(int &flow, int &cost) {
		for (int i = 0; i < n; i++) d[i] = INF;
		memset(inq, 0, sizeof inq);
		d[s] = 0, a[s] = INF, inq[s] = true;
		queue<int> Q; Q.push(s);
		while (!Q.empty()) {
			int u = Q.front(); Q.pop();
			inq[u] = false;
			for (int& idx : G[u]) {
				E &e = edges[idx];
				if (e.cp && d[e.to] > d[u] + e.v) {
					d[e.to] = d[u] + e.v;
					p[e.to] = idx;
					a[e.to] = min(a[u], e.cp);
					if (!inq[e.to]) {
						Q.push(e.to);
						inq[e.to] = true;
					}
				}
			}
		}
		if (d[t] == INF) return false;
		flow += a[t];
		cost += a[t] * d[t];
		int u = t;
		while (u != s) {
			edges[p[u]].cp -= a[t];
			edges[p[u] ^ 1].cp += a[t];
			u = edges[p[u]].from;
		}
		return true;
	}

	pii go() {
		int flow = 0, cost = 0;
		while (BellmanFord(flow, cost));
		return pii(flow, cost);
	}
} MM;

int dfs(int u1, int u2) {
	if (~dp[u1][u2])return dp[u1][u2];
	if (G1[u1].size() != G2[u2].size())return dp[u1][u2] = 999;
	for (int v1 : G1[u1]) {
		for (int v2 : G2[u2]) {
			dfs(v1, v2);
		}
	}
	int S = 0, T = 2 * n + 1;
	MM.init(2 * n + 2, S, T);
	for (int v : G1[u1])MM.addedge(S, v, 1, 0);
	for (int v : G2[u2])MM.addedge(v + n, T, 1, 0);
	for (int v1 : G1[u1]) {
		for (int v2 : G2[u2]) {
			MM.addedge(v1, v2 + n, 1, dp[v1][v2]);
		}
	}
	int res = MM.go().second;
	if (u1 != u2)res++;
	return dp[u1][u2] = min(res, 999);
}
int main() {
	scanf("%d", &n);
	memset(dp, -1, sizeof(dp));
	for (int i = 1; i <= n; i++) {
		int f;
		scanf("%d", &f);
		if (f)G1[f].push_back(i);
		else r1 = i;
	}
	for (int i = 1; i <= n; i++) {
		int f;
		scanf("%d", &f);
		if (f)G2[f].push_back(i);
		else r2 = i;
	}
	printf("%d\n", dfs(r1, r2));
	return 0;
}

I - Tournament

题意：有 n 支队伍，任意两队都有一场比赛，问如何安排，使得所有队伍的第一场与最后一场比赛的间隔时间之和最短。

构造

必须要尽量均匀地分配时间。

把所有队伍分成两组，在最开始和最后都是组内比赛，中间进行组间比赛。

因为要均匀分配，所以要使得最后结束的队伍尽量先开始，最先开始的队伍尽量先结束。例如队伍 1 先开始，则在 1 的最后一场比赛前安排总场次-1 场 2 的比赛、总场次-2 场 3 的比赛、总场次-3 场 4 的比赛。队伍 8 后结束，则在队伍 8 后安排 1 场 7 的比赛，2 场 6 的比赛，···。

#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int T;
int n;
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n / 2; i++) {
			for (int j = 1; j < i; j++)printf("%d %d\n", i, j);
		}
		for (int i = n / 2 + 1; i < n; i++) {
			for (int j = 1; j <= n - i; j++)printf("%d %d\n", i, j);
		}
		for (int i = 1; i <= n / 2; i++) {
			for (int j = n - i + 1; j <= n; j++)printf("%d %d\n", i, j);
		}
		for (int i = n / 2 + 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++)printf("%d %d\n", i, j);
		}
	}
	return 0;
}

C - Decrement on the Tree

题意：给定一棵带边权的树，每次操作选择一条路径，路径上所有边权减 1，问最少几次操作使得所有边权为 0。有多次修改边权，每次修改后都要求给出答案。

思维

把边上问题转化为点上问题。

考虑一条路径，我们关心的只是它的两个端点。那么就枚举每一个点，看有多少条路径以它作为一个端点。最终答案就是每点的答案之和 / 2.

如果以一点为端点的边的边权中的最大值大于以该点为端点的边的边权之和的一半，那么该点必定需要有路径从该点出去。

如果该点边权之和为奇数，则需要一条路径。否则不需要。

#include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
int n, q;
struct E
{
	int u, v, w;
}es[N];
multiset<int, greater<int> >st[N];
ll sum[N], ans;
int cal(int u) {
	int mx = *st[u].begin();
	if (2 * mx > sum[u])return 2 * mx - sum[u];
	else return (sum[u] & 1);
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i < n; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		es[i] = { u,v,w };
		st[u].insert(w);
		st[v].insert(w);
		sum[u] += w;
		sum[v] += w;
	}
	for (int i = 1; i <= n; i++) {
		ans += cal(i);
	}
	printf("%lld\n", ans / 2);
	while (q--) {
		int p, w;
		scanf("%d%d", &p, &w);
		int u = es[p].u, v = es[p].v;
		ans -= cal(u);
		st[u].erase(st[u].find(es[p].w));
		sum[u] -= es[p].w;
		st[u].insert(w);
		sum[u] += w;
		ans += cal(u);
		ans -= cal(v);
		st[v].erase(st[v].find(es[p].w));
		sum[v] -= es[p].w;
		st[v].insert(w);
		sum[v] += w;
		ans += cal(v);
		es[p].w = w;
		printf("%lld\n", ans / 2);
	}
	return 0;
}