#C240924A. 避难

标签（Label）

前言（Front talk)

推荐一篇文章：冷门科技——DFS 序求 LCA

网址（Website）

题目详情 - 避难 - Super

题解 - 避难 - Super

题解（Solution）

$\qquad$ 将点按照它到上方第一个避难点的距离排序，那么最优的设置方法为设置在最大的 $k$ 个点的 $LCA$ 处，实现一个 $LCA$ 算法即可。

代码（Code）

给出两份代码，一份是使用dfn序求lca，一份是用倍增求lca。

dfn序求lca

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
bool ST;

int n,m,q,ans,dan[N];
vector<P> ft[N];
bool r[N];

int f[N][24],dfn[N],idx;
int dis[N],d[N];//到避难所的距离 、到根节点的距离 
inline void dfs_pre(int x,int fa){
	f[dfn[x]=++idx][0] = fa;
	
	if(r[x]) dis[x] = 0;
	for(auto p:ft[x]){
		int y = p.x, v = p.y;
		if(y==fa) continue;
		dis[y] = dis[x]+v, 
		d[y] = d[x]+v,
		dfs_pre(y,x);
	}
}

inline int cmn(int x,int y){return dfn[x] < dfn[y] ? x : y;}
inline int lca(int x,int y){
	if(x==y) return x;
	if((x=dfn[x]) > (y=dfn[y])) swap(x,y);
	int d = __lg(y-x++);
	return cmn(f[x][d], f[y-(1<<d)+1][d]);
}

#define get fnawv94nf4fmvzso
inline int get(int k){
	sort(dan+1,dan+k+1,[&](int x,int y){return dis[x]>dis[y];});//对剩下的儿子排序 
	int F = dan[1], di = dis[dan[1]];
	int res = inf;dan[k+1]=0;
	For(i,1,k){
		int x = dan[i];F = lca(F,x);
		di = max(di, d[dan[i]]);
		int ans = max(di-d[F],dis[dan[i+1]]);
		if(res<=ans) break;
		res = ans;
	}return res;
}


bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
//	freopen("ex_disaster2.in","r",stdin);
	freopen("disaster.in","r",stdin);
	freopen("disaster.out","w",stdout);	
	cin>>n>>m>>q;int Tim = clock();
	For(i,1,m) r[rd()] = true;r[1] = true;
	For(i,1,n-1){
		int x,y,v;cin>>x>>y>>v;
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}
	
	dfs_pre(1,0);
	For(j,1,__lg(n)) for(int i=1;i+(1<<j)-1<=n;i++)
		f[i][j] = cmn(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	
	while(q--){
		int k = rd();For(i,1,k) cin>>dan[i];
		if(k==1){cout<<0<<'\n';continue;}
		cout<<get(k)<<'\n';
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}

倍增求lca

注意第 $53$ 行，对时间的优化十分重要。

#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
bool ST;

int n,m,q,ans,dan[N];
vector<P> ft[N];
bool r[N];

int f[N][24],dep[N];
int dis[N],d[N];//到避难所的距离 、到根节点的距离 
inline void dfs_pre(int x,int fa){
	dep[x] = dep[fa]+1, f[x][0] = fa;
	For(j,1,21) f[x][j] = f[f[x][j-1]][j-1];
	
	if(r[x]) dis[x] = 0;
	for(auto p:ft[x]){
		int y = p.x, v = p.y;
		if(y==fa) continue;
		dis[y] = dis[x]+v, 
		d[y] = d[x]+v,
		dfs_pre(y,x);
	}
}

inline int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	Rof(i,21,0) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	if(x==y) return x;
	Rof(i,21,0) if(f[x][i]!=f[y][i]) x = f[x][i], y = f[y][i];
	return f[x][0];
}

#define get fnawv94nf4fmvzso
inline int get(int k){
	sort(dan+1,dan+k+1,[&](int x,int y){return dis[x]>dis[y];});//对剩下的儿子排序 
	int F = dan[1], di = dis[dan[1]];
	int res = inf;dan[k+1]=0;
	For(i,1,k){
		int x = dan[i];F = lca(F,x);
		di = max(di, d[dan[i]]);
		int ans = max(di-d[F],dis[dan[i+1]]);
		if(res<=ans) break;res = ans;
	}return res;
}


bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
//	freopen("ex_disaster2.in","r",stdin);
	freopen("disaster.in","r",stdin);
	freopen("disaster.out","w",stdout);	
	cin>>n>>m>>q;int Tim = clock();
	For(i,1,m) r[rd()] = true;r[1] = true;
	For(i,1,n-1){
		int x,y,v;cin>>x>>y>>v;
		ft[x].emplace_back(y,v);
		ft[y].emplace_back(x,v);
	}
	
	dfs_pre(1,0);
	
	while(q--){
		int k = rd();For(i,1,k) cin>>dan[i];
		if(k==1){cout<<0<<'\n';continue;}
		cout<<get(k)<<'\n';
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}