求调
查看原帖
求调
1203411
Louis_lxy楼主2024/5/31 21:53
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 1;
int n, m, len, head[N], l = 0, r = 1e5, f[N][20], w[N][20], a[N];
bitset<N> can;
struct node { int v, w, next; } e[N];

void add(int u, int v, int w)
{
	e[++len] = node{ v, w, head[u] };
	head[u] = len;
}

void dfs(int u, int fa)
{
	f[u][0] = fa;
	for (int i = head[u]; i; i = e[i].next)
	{
		w[e[i].v][0] = e[i].w;
		dfs(e[i].v, u);
	}
}

bool cango(int u)
{
	if (can[u]) return false;
	if (head[u] == 0) return true;
	bool flag = 0;
	for (int i = head[u]; i; i = e[i].next)
		flag |= cango(e[i].v);
	return flag;
}

bool check(int t)
{
	can = 0;
	for (int i = 1; i <= m; ++i)
	{
		int x = a[i], cnt = 0;
		for (int j = 19; ~j; --j)
			if (f[x][j] > 1 && cnt + w[x][j] <= t)
				x = f[x][j], cnt += w[x][j];
		can[x] = 1;
	}
	return !cango(1);
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; ++i)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		add(u, v, w);
	}
	dfs(1, 0);
	for (int j = 1; j < 20; ++j)
		for (int i = 1; i <= n; ++i)
		{
			f[i][j] = f[f[i][j - 1]][j - 1];
			w[i][j] = w[i][j - 1] + w[f[i][j - 1]][j - 1];
		}
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) scanf("%d", &a[i]);
	bool ok = 0;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid, ok = 1;
		else l = mid + 1;
	}
	if (ok) printf("%d", r);
	else printf("-1");
	return 0;
}
2024/5/31 21:53
加载中...