洛谷P1084 树上问题，思维，贪心，二分答案

题意：

$H$国有$n$个城市，用$n-1$条道路连接着，其中$1$是首都，发生了疫情，为了使边境城市（叶子结点）不被感染，需要在所有从首都通往边境城市的路上设置至少一个检查站，一个检查站需要一个军队管辖。$H$国有$m$个军队，目前分别驻扎在$a_i$城市，现在可以调遣军队，他们同时出发，问最快能在什么时候使所有首都通往边境城市的道路上都至少存在一个检查站？军队每个小时行进$1$个单位的距离

Solution：

如果检查站深度越低，显然他能为更多的道路做出贡献，因此，军队要么被调拨至$1$的其他儿子处，要么在当前位置到$1$的链的深度更浅的位置，这样的决策一定是更优的，有点难操作，相互制约因素有点多，我们要使耗时最多的军队耗时最少，不妨二分答案，假设二分时间为$x$，考虑怎么检查是否在$x$时间内达成目的

由于深度越低，贡献越大，所以我们不妨在$x$时间内，一直向上走，由上面的分类，我们可以考虑是否让某只军队$i$越过$1$这个位置，设$u$为$1$的儿子中，子树包含了$a_i$的城市

如果$x$时间并不足以让$i$到达$1$，那么他最高能到达哪里，他在这个位置就一定最优

如果$x$时间足以让$i$到达$1$，设到达$1$位置后还剩下的时间为$rest$，这样的军队能够被调拨至$1$的另外的儿子处，同时，它也可以重新返回$u$，管辖他所在的那一颗子树，我们该怎么决策呢？可以这样考虑，我们将所有能够到达$1$的$i$的$rest$排序，再将所有$1$到他所有没有被管辖的儿子的距离排序，现在要做的就是用$rest$跟距离配对。贪心想法自然是小的配对小的，大的配对大的，尽量物尽其用，但此时如果可以返回$u$，并且如果$u$没有被管辖，返回$u$一定是更优的，证明过程如下：

我们的配对顺序如下

bool check()
{
    sort(rest+1,rest+1+n);
    sort(dis+1,dis+1+m);
    for(int i=1,j=1;i<=n;i++)
        if(j<=m&&rest[i]>=dis[j]) j++;
    return j==m+1;
}
1
2
3
4
5
6
7
8

显然，我们配对过的$j$一定是从左到右的，所以如果$i$的$u$还没有被配对，此时一定出现在已配对完指针的右边，由于$dis$被排过序，他的$dis$一定大于等于现在等待匹配的，也就是我们能用目前的$rest[i]$，来消去一个不会更小的$dis[j]$，这样一定是更赚的，这是没有$i$返回过的情况，同理可以得到，就算有$i$返回过，也是更赚的

最后，能否在$x$时间内到达$1$，只需要看深度即可，并且需要处理每个$i$的$u$，需要一步一步往上走，直到父亲为$1$为止，这一步是可以用倍增优化的，但是需要注意的是，此时是有权树，倍增跳跃的距离不是$2^i$。同时，处理完所有不能到达$1$的军队之后，我们还需要检查子树是否被管辖，所以需要一次$dfs$，子树$u$被管辖的条件是：$u$有军队，或者$u$的所有儿子都被管辖。

// #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

using ll=long long;
#define int long long
const int N=5e4+5,inf=0x3fffffff;
const long long INF=0x3f3f3f3f3f3f,mod=998244353;

struct way
{
	int to,next,w;
}edge[N<<1];
int cntt,head[N];

void add(int u,int v,int w)
{
	edge[++cntt].to=v;
	edge[cntt].w=w;
	edge[cntt].next=head[u];
	head[u]=cntt;
}

bool has[N];
int n,m,depth[N],a[N],f[N][21];

void dfs(int u,int fa)
{
	f[u][0]=fa;
	for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to,w=edge[i].w;
		if(v==fa) continue;
		depth[v]=depth[u]+w;
		dfs(v,u);
	}
}

struct node
{
	int rest,from;
}rt[N];

int now[N],cnt;

int jump(int x,int len)
{
	for(int i=20;i>=0;i--)
		if(f[x][i]&&depth[x]-depth[f[x][i]]<=len) len-=depth[x]-depth[f[x][i]],x=f[x][i];
	return x;
}

void dfs1(int u,int fa)
{
	bool flag=true,son=false;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v==fa) continue;
		dfs1(v,u); son=true;
		if(!has[v]) flag=false;
	}
	has[u]=(has[u]||(son&&flag));
}

bool check(vector<pair<int,int>>&tmp)
{
	int j=0;
	for(int i=1;i<=cnt;i++)
	{
		while(j<tmp.size()&&has[tmp[j].first]) j++;
		if(!has[rt[i].from]) has[rt[i].from]=true;
		else if(j<tmp.size()&&rt[i].rest>=tmp[j].second) has[tmp[j++].first]=true;
	}
	while(j<tmp.size()&&has[tmp[j].first]) j++;
	return j==tmp.size();
}

bool check(ll x)
{
	cnt=0;
	for(int i=1;i<=n;i++) has[i]=false;
	for(int i=1;i<=m;i++)
	{ 
		if(depth[a[i]]-1<=x) rt[++cnt]={x-(depth[a[i]]-1),jump(a[i],depth[a[i]]-2),false};
		else has[jump(a[i],x)]=true;
	}
	dfs1(1,0);
	sort(rt+1,rt+1+cnt,[&](const node& x,const node& y){
		return x.rest<y.rest;
	});
	vector<pair<int,int>>tmp;
	for(int i=head[1];i;i=edge[i].next)
		if(!has[edge[i].to]) tmp.push_back({edge[i].to,edge[i].w});
	sort(tmp.begin(),tmp.end(),[&](const pair<int,int>& x,const pair<int,int>& y){
		return x.second<y.second;
	});
	return check(tmp);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n; depth[1]=1;
	for(int i=1;i<n;i++)
	{
		int u,v,w; cin>>u>>v>>w;
		add(u,v,w); add(v,u,w);
	}
	cin>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	dfs(1,0);
	ll l=1,r=INF,ans=INF;
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	if(ans==INF) ans=-1;
	cout<<ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138