题解P1084 【疫情控制】
这道题是贪心+树上倍增实现的，好像没有拿部分分数的方法。
本题题意是，给一棵有根树，以及若干个出发点，做题的人自己为这些出发点一一规定终点，使得：所有结点都被这些终点标记过（规定“被标记过”有三种情况，①这个节点本身就是终点，②这个节点位于某个终点的子树里，③这个节点的所有子节点都被标记过），并且在这些出发点中，耗费时间最长抵达终点的节点耗费的时间最短。
一看要寻找最大值最小，就联想到了二分。这样，问题就被转化成判定k时间之内，是否存在着一种终点方案使得所有节点都被标记过。
现在来贪心的思考一下终点怎么选择是最优的。画图可以发现，最好是不要跨根选择终点，先把本子树搞好，并且当所有的终点尽可能选择靠近根节点的时候，能够标记最多的节点，应该一直往上跳。假如一棵以根节点的儿子为根的树已经被标记过，而在这棵树里面有一个还没有分配的出发点有能力走到根节点甚至还有富裕，那么这个节点的终点就可以去解救别的这样的树，另开几个数组存储有能力救人的节点/需要解救的节点和它们还能走的距离/还差的距离，又贪心的按照从小到大匹配就可以了。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//链式前向星存图法
int ecnt, head[50007], to[100007], weight[100007], next[100007];
void add(int u, int v, int w){
to[++ecnt]=v;
weight[ecnt]=w;
next[ecnt]=head[u];
head[u]=ecnt;
return ;
}
//DFS求树上倍增到达的节点，需要耗费的时间
int anc[50007][17], cost[50007][17];
void dfs(int u){
for(int i=1; i<17; i++){
anc[u][i]=anc[anc[u][i-1]][i-1];
cost[u][i]=cost[u][i-1]+cost[anc[u][i-1]][i-1];
if(anc[u][i]==0){
break;
}
}
for(int i=head[u]; i; i=next[i]){
int v=to[i];
if(v!=anc[u][0]){
anc[v][0]=u;
cost[v][0]=weight[i];
dfs(v);
}
}
return ;
}
//处理这些节点到底有没有被标记
int n, m;
int army[50007];
bool isok[50007];
void fisok(int u){
bool f=0;
for(int i=head[u]; i; i=next[i]){
int v=to[i];
if(v!=anc[u][0]){
fisok(v);
if(isok[v]==0 && u!=1){
return ;
}
else{
f=1;
}
}
}
isok[u]=f;
return ;
}
//有能力救人/待解救
struct node{
int left, x;
friend bool operator < (node n1, node n2){
return n1.left<n2.left;
}
}arrive[50007], unarrive[50007];
//二分的时候的判定函数
bool chk(int k){
memset(isok, 0, sizeof(isok));
int arrcnt=0, unarrcnt=0;
for(int i=1; i<=m; i++){
int cur=army[i], t=0;
//尽可能往上跳
for(int j=16; j>=0; j--){
if(anc[cur][j] && cost[cur][j]+t<=k){
t+=cost[cur][j];
cur=anc[cur][j];
}
}
//走不到根就到此为止吧
if(cur!=1){
isok[cur]=1;
}
//找走到根之前的第一个点，处理剩余能走的路程
else{
arrive[++arrcnt].left=k-t;
cur=army[i];
for(int j=16; j>=0; j--){
if(anc[cur][j]>1){
cur=anc[cur][j];
}
}
arrive[arrcnt].x=cur;
}
}
fisok(1);
//处理需要解救的节点仍然需要的时间
for(int i=head[1]; i; i=next[i]){
int v=to[i];
if(isok[v]==0){
unarrive[++unarrcnt].left=weight[i];
unarrive[unarrcnt].x=v;
}
}
//无论如何也匹配不成功
if(unarrcnt>arrcnt){
return 0;
}
sort(arrive+1, arrive+1+arrcnt);
sort(unarrive+1, unarrive+1+unarrcnt);
//小对小大对大好好匹配
int ind=1;
for(int i=1; i<=arrcnt; i++){
if(isok[arrive[i].x]==0){
isok[arrive[i].x]=1;
}
else{
if(unarrive[ind].left<=arrive[i].left){
isok[unarrive[ind].x]=1;
ind++;
}
}
while(isok[unarrive[ind].x] && ind<=unarrcnt){
ind++;
}
}
if(ind<=unarrcnt){
return 0;
}
return 1;
}
int main(){
scanf("%d", &n);
for(int i=1; i<n; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
dfs(1);
scanf("%d", &m);
for(int i=1; i<=m; i++){
scanf("%d", &army[i]);
}
int chkcnt=0;
for(int i=head[1]; i; i=next[i]){
chkcnt++;
}
//永远也不可能成功
if(chkcnt>m){
printf("-1");
}
else{
int l=0, r=2e9, ans;
while(l<=r){
int mid=(l+r)>>1;
if(chk(mid)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
printf("%d", ans);
}
return 0;
}