妹子刚学OI1s90分求助
查看原帖
妹子刚学OI1s90分求助
41515
OOmegakkksn03楼主2020/1/31 00:09

#7WA了

#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int mn = 50050;
vector <int> ed[mn],len[mn];
int n,m,a[mn][20],ar[mn],cnt,cnt2,cnt3,Fa[mn];
bool abl[mn],lf[mn],rqr[mn];
long long dep[mn] = {-50000000000086ll},cap[mn],ned[mn],wat[mn];

void dfs(int x)
{
	int lth = ed[x].size();
	for (int i = 1;a[x][i-1];i++)
		a[x][i] = a[a[x][i-1]][i-1];
	for (int i = 0;i < lth;i++)
		if (ed[x][i] != a[x][0])
		{
			a[ed[x][i]][0] = x;
			Fa[ed[x][i]] = (x == 1?ed[x][i]:Fa[x]);
			dep[ed[x][i]] = dep[x]+len[x][i];
			dfs(ed[x][i]);
		}
	if (x != 1 && lth == 1) lf[x] = true;
	ed[x].clear();
	len[x].clear();
}

bool chk(int x)
{
	if (abl[x]) return true;
	if (Fa[x] != x) return abl[x] = chk(a[x][0]);
	if (wat[x] == 0) ned[cnt2++] = dep[x];
	else wat[x] = 0;
	return abl[x] = true;
}

bool can(long long ste)
{
	memset(abl,false,sizeof(abl));
	memset(wat,0,sizeof(wat));
	cnt = 0,cnt2 = 0;
//cout << ste << ":\n";
	for (int i = 0;i < m;i++)
		if (ste > dep[ar[i]])
			if (ste>=dep[ar[i]]+dep[Fa[ar[i]]])
				cap[cnt++] = ste-dep[ar[i]];
			else if (wat[Fa[ar[i]]])
					if (wat[Fa[ar[i]]] > ste-dep[ar[i]])
						cap[cnt++] = wat[Fa[ar[i]]],
						wat[Fa[ar[i]]] = ste-dep[ar[i]];
					else cap[cnt++] = ste-dep[ar[i]];
				else wat[Fa[ar[i]]] = ste-dep[ar[i]];
		else
		{
			long long st = ste;
			int d = ar[i];
			for (int j = 15;j >= 0;j--)
				if (st >= dep[d]-dep[a[d][j]])
					d = max(a[d][j],Fa[d]),st -= dep[d]-dep[a[d][j]];
//cout << d << '\n';
			abl[d] = true;
		}
//for (int i = 1;i <= n;i++) cout << wat[i] << ' ';
//cout << '\n';	
	for (int i = 1;i <= n;i++) if (lf[i]) chk(i);
	for (int i = 1;i <= n;i++)
		if (wat[i]) cap[cnt++] = wat[i];
	if (cnt2 > cnt) return false;
	sort(cap,cap+cnt);
	sort(ned,ned+cnt2);
//for (int i = cnt-1;i >= 0;i--) cout << cap[i] << ' ';
//cout << '\n';
//for (int i = cnt2-1;i >= 0;i--) cout << ned[i] << ' ';
//cout << '\n';
//	if (cnt2 > cnt) return false;
	while (--cnt2 >= 0)
		if (cap[--cnt] < ned[cnt2]) return false;
	return true;
}

int main()
{
//	freopen("x.txt","r",stdin);
	scanf("%d",&n);
	for (int i = 0;i < n-1;i++)
	{
		int s,e,l;
		scanf("%d%d%d",&s,&e,&l);
		ed[s].push_back(e);
		len[s].push_back(l);
		ed[e].push_back(s);
		len[e].push_back(l);
	}
	dfs(1);
//	for (int i = 1;i <= n;i++)
//		cout << Fa[i] << ' ';
//	cout << '\n';
	scanf("%d",&m);
	for (int i = 0;i < m;i++)
		scanf("%d",&ar[i]);
	long long l = 0,r = 50000000000086ll;
	while (l != r)
		if (can((l+r)/2)) r = (l+r)/2;
		else l = (l+r)/2+1;
	if (r == 50000000000086ll) cout << -1;
	else cout << r;
}
2020/1/31 00:09
加载中...