60pts求调
查看原帖
60pts求调
999274
CNS_5t0_0r2楼主2024/7/21 09:37
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 9,LOGN = 20;
int n,m,Log2;
int l,r,ans = -1;
int a[N];
struct edge{
	int to,cost,nex;
} e[N << 1];
int head[N],ecnt;
void addedge(int u,int v,int w){
	ecnt++;
	e[ecnt] = (edge){v,w,head[u]};
	head[u] = ecnt;
}
int anc[N][LOGN],dis[N][LOGN];
void dfs1(int u,int fa,int last){
	anc[u][0] = fa;dis[u][0] = last;
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to,w = e[i].cost;
		if(v == fa)
			continue;
		dfs1(v,u,w);
	}
}
void init(){
	for(int i = 1;i <= Log2;i++){
		for(int j = 1;j <= n;j++){
			anc[j][i] = anc[anc[j][i - 1]][i - 1];
			dis[j][i] = dis[j][i - 1] + dis[anc[j][i - 1]][i - 1];
		}
	}
}

int remain[N],r_top;//剩余未被管辖的节点
bool cmp1(int x,int y){
	return dis[x][0] < dis[y][0];
}

struct node{
	int ch,rest;
} rec[N],rec2[N];
int rec_top,rec2_top;
bool cmp2(node x,node y){
	return x.rest < y.rest;
}
bool cmp3(node x,node y){
	return x.rest - dis[x.ch][0] < y.rest - dis[y.ch][0];
}

bool vis[N];//节点是否被管辖
bool is_remain[N];//根的子节点是否未被管辖
bool dfs2(int u){
	if(vis[u])
		return true;
	int child = 0;
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to;
		if(v == anc[u][0])
			continue;
		if(!dfs2(v))
			return false;
		child++;
	}
	return child;
}
void clear(){
	rec_top = rec2_top = r_top = 0;
	memset(vis,0,sizeof vis);
	memset(is_remain,0,sizeof is_remain);
}
bool check(int lim){
	clear();
	for(int i = 1;i <= m;i++){
		int u = a[i],tot = 0;
		//上提军队
		for(int j = Log2;j >= 0;j--){
			if(anc[u][j] > 1/*不能跳到根*/ && tot + dis[u][j] <= lim){
				u = anc[u][j];
				tot += dis[u][j];
			}
		}
		if(anc[u][0] == 1 && tot + dis[u][0] <= lim)
			rec[++rec_top] = (node){u,lim - tot};
		else
			vis[u] = true;
	}
	for(int i = head[1];i;i = e[i].nex){
		int v = e[i].to;
		is_remain[v] = !dfs2(v);
	}
	
	
	sort(rec + 1,rec + rec_top + 1,cmp3);
	for(int i = 1;i <= rec_top;i++){
		if(is_remain[rec[i].ch] && rec[i].rest - dis[rec[i].ch][0] < dis[rec[i].ch][0])
			is_remain[rec[i].ch] = false;
		else
			rec2[++rec2_top] = rec[i];
	}
	for(int i = head[1];i;i = e[i].nex){
		int v = e[i].to;
		if(is_remain[v])
			remain[++r_top] = v;
	}
	sort(remain + 1,remain + r_top + 1,cmp1);
	
	int i = 1,j = 1;
	while(j <= r_top){
		while(i <= rec2_top && rec2[i].rest - dis[rec2[i].ch][0] < dis[remain[j]][0])
			i++;
		if(i > rec2_top)
			return false;
		i++;j++;
	}

	return true;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	Log2 = ceil(log2(n));
	for(int i = 1;i < n;i++){
		int u,v,w;
		cin >> u >> v >> w;
		addedge(u,v,w);
		addedge(v,u,w);
		r += w;
	}
	dfs1(1,0,0);
	init();
	cin >> m;
	for(int i = 1;i <= m;i++)
		cin >> a[i];
	l = 1;
	while(l <= r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	cout << l;
	return 0;
}
2024/7/21 09:37
加载中...