求助
查看原帖
求助
671774
LUlululu1616楼主2023/11/8 13:54

用的树形 dp 做法,感觉没啥毛病,求调

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(2)
using namespace std;
const int maxn = 2e5 + 5, mod = 1e9 + 7;
int n, m, ps[maxn], use[maxn], cnt, mx[maxn], p[maxn], smx[maxn], ans[maxn];
vector<int> e[maxn];
void dfs(int u, int fa) {
	for (int i = 0; i < e[u].size(); i++) {
		int v = e[u][i];
		if(v == fa)
			continue;
		dfs(v, u);
		use[u] |= use[v];
	}
	cnt += use[u];
}
void dfs1(int u, int fa) {
//	cout << u << endl;
	for (int i = 0; i < e[u].size(); i++) {
		int v = e[u][i];
		if(v == fa || !use[v])
			continue;
		dfs1(v, u);
		if(smx[u] < mx[v])
			smx[u] = mx[v];
		if(mx[u] < smx[u])
			swap(mx[u], smx[u]), p[u] = v; 
	}
	mx[u]++, smx[u]++;
}
void dfs2(int u, int fa, int out) {
	ans[u] = max(mx[u], out);
	for (int i = 0; i < e[u].size(); i++) {
		int v = e[u][i];
		if(v == fa || !use[v])
			continue;
		dfs2(v, u, max(out, (p[u] == v ? smx[u] : mx[u])));
	}
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for (int i = 1; i <= m; i++)
		cin >> ps[i], use[ps[i]] = 1;
	dfs(ps[1], 0);
	cnt--;
	dfs1(ps[1], 0);
	dfs2(ps[1], 0, 0);
	int mx = 0, p = 0;
	for (int i = 1; i <= n; i++)
		if(mx < ans[i])
			mx = ans[i], p = i;
	cout << p << endl << cnt * 2 - mx + 1 << endl;
	return 0;
}
2023/11/8 13:54
加载中...