50pts WA on #5 #7 #8 #9 #10 求调
查看原帖
50pts WA on #5 #7 #8 #9 #10 求调
753068
EchoHua0402楼主2024/3/10 11:31

rt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;
const int K=30;
int n,m;
int mili[N];
int dep[N],fa[N][K];
ll dis[N][K];
bool vis[N];
struct edge
{
	int v;
	ll w;
};
vector<edge> G[N];
struct node
{
	int u;
	ll w;
}a[N],b[N];
int cnta=0,cntb=0;
bool cmp(node a,node b)
{
	return a.w<b.w;
}
void dfs1(int u,int fu)
{
	fa[u][0]=fu;
	dep[u]=dep[fu]+1;
	for (edge e:G[u])
	{
		int v=e.v;
		ll w=e.w;
		if (v==fu) continue;
		dis[v][0]=w;
		dfs1(v,u);
	}
}
void dfs2(int u,int fu)
{
	if (vis[u]) return ;
	vis[u]=1;
	bool leaves=1;
	for (edge e:G[u])
	{
		int v=e.v;
		if (v==fu) continue;
		leaves=0;
		dfs2(v,u);
		vis[u]=vis[u]&vis[v];
	}
	if (leaves) vis[u]=0;
}
void work()
{
	for (int j=1;j<K;j++)
	{
		for (int i=1;i<=n;i++)
		{
			fa[i][j]=fa[fa[i][j-1]][j-1];
			dis[i][j]=dis[i][j-1]+dis[fa[i][j-1]][j-1];
		}
	}
}
bool jump(int u,ll x)
{
	ll sum=0;
	for (int i=K-1;i>=0;i--)
	{
		if (fa[u][i]>1&&sum+dis[u][i]<=x)
		{
			sum+=dis[u][i];
			u=fa[u][i];
		}
	}
	if (fa[u][0]==1&&sum+dis[u][0]<=x)
	{
		cnta++;
		a[cnta].w=x-sum-dis[u][0];
		a[cnta].u=u;
		return 0;
	}
	return 1;
}
bool check(ll x)
{
	memset(vis,0,sizeof(vis));
	cnta=cntb=0;
	for (int i=1;i<=m;i++) vis[mili[i]]=jump(mili[i],x);
	dfs2(1,0);
	if (vis[1]) return true;
	for (edge e:G[1])
	{
		int v=e.v;
		ll w=e.w;
		if (!vis[v])
		{
			cntb++;
			b[cntb].w=w;
			b[cntb].u=v;
		}
	}
	sort(a+1,a+cnta+1,cmp);
	sort(b+1,b+cntb+1,cmp);
	if (cnta<cntb) return false;
	int now=1;
	for (int i=1;i<=cnta;i++)
	{
		if (!vis[a[i].u]) vis[a[i].u]=1;
		else if (a[i].w>=b[now].w) vis[b[now].u]=1;
		while (vis[b[now].u]&&now<=cntb) now++;
		if (now>cntb) return true;
	}
	if (now>cntb) return true;
	return false;
}
ll find(ll l,ll r)
{
	ll ans=-1;
	while (l<=r)
	{
		ll mid=(l+r)>>1;
		if (check(mid))
		{
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	return ans;
}
int main()
{
	cin>>n;
	int u,v,w;
	for (int i=1;i<n;i++)
	{
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	cin>>m;
	for (int i=1;i<=m;i++) cin>>mili[i];
	dfs1(1,0);
	work();
	cout<<find(0,1e13)<<endl;
	return 0;
}
2024/3/10 11:31
加载中...