【悬赏关注】50pts求调
查看原帖
【悬赏关注】50pts求调
999274
CNS_5t0_0r2楼主2024/7/20 11:28
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 9,LOGN = 20;
bool debug;
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 i,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++;
	}
	if(!child)
		return false;
	return true;
}
void clear(){
	rec_top = rec2_top = r_top = 0;
	memset(vis,0,sizeof vis);
}
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){i,u,lim - tot};
		else
			vis[u] = true;
	}
	for(int i = head[1];i;i = e[i].nex){
		int v = e[i].to;
		if(!dfs2(v))
			is_remain[v] = true;
	}
	
	
	sort(rec + 1,rec + rec_top + 1,cmp2);
	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;
	sort(rec2 + 1,rec2 + rec2_top + 1,cmp3);
	if(debug){
		cout << "闲置军队:\n";
		for(int k = 1;k <= rec2_top;k++)
			cout << '(' << rec2[k].ch << ',' << rec2[k].rest << ')' << ' ';
		cout << '\n';
		cout << "还有以下节点未被管辖:\n";
		for(int k = 1;k <= r_top;k++)
			if(is_remain[remain[k]])
				cout << remain[k] << ' ';
		cout << '\n';
	}
	
	
	while(i <= rec2_top && j <= r_top){
		if(rec2[i].rest - dis[rec2[i].ch][0] >= dis[remain[j]][0]){
			is_remain[remain[j]] = false;
			j++;
		}
		i++;
	}
	if(debug){
		cout << "闲置军队:\n";
		for(int k = i;k <= rec2_top;k++)
			cout << '(' << rec2[k].ch << ',' << rec2[k].rest << ')' << ' ';
		cout << '\n';
		cout << "还有以下节点未被管辖:\n";
		for(int k = 1;k <= r_top;k++)
			if(is_remain[remain[k]])
				cout << remain[k] << ' ';
		cout << '\n';
	}
	for(int i = head[1];i;i = e[i].nex){
		int v = e[i].to;
		if(is_remain[v])
			return false;
	}
	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;
		//	debug = true;
		if(debug){
			cout << "\n\n";
			//cout << l << ' ' << r << ' ';
			cout << mid << '\n';
		}
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}
		else
			l = mid + 1;
	}
	cout << ans;
	return 0;
}
2024/7/20 11:28
加载中...