题解 P6058 【[加油武汉]体温调查】

· · 题解

二分答案！！！

比赛时看到此题仔细琢磨，感觉和NOIP 2018赛道修建有些类似

都是在分一定段的前提下使某个值尽可能地小（大）。

二分答案：显然是对需要时间最长的人所需要的时间，即要求的答案 ans 进行二分。

如果 ans 越大，那么每个人可以访问到的节点就一定不会更少，需要的人力就越少，答案具有可二分性。

所以对于每个mid，我们求出所需要的的人数x，

如果x <= k，说明在规定时间内完成任务，则接着在左半边找；

如果x > k，说明在规定时间完不成任务，则接着在右半边找。

问：在每次check()时，我们想让一个人到达尽可能多的叶子节点，如何快速的求出从叶子s能到达的距s最远的节点呢？

答：二分答案！

这一点与赛道修建比较相似，在总的二分答案的check中再次二分。

设 s 走到 t 花费时间 time，

若 time <= ans 则说明时间没用完，在 t 到 tot之间找；

若 time > ans 则说明时间不够用，在s 到 tot之间找。

显然在寻找最远能走到的叶子的过程中，也具有可二分性。

这里其实还有一个小问题：

如何快速地（O(1)）求出两个叶子之间的距离呢？

设 dis_i 表示 i 到 root 的距离，

对于树上任意两点 i , j ，

它们之间的距离为 :

dis_i$ + $dis_j$ - 2*$dis_{LCA(i,j)} 设 $s_i$ 表示从第一个叶子节点到第 $i$ 个节点间的距离， 若一个人把 $i$ 到 $j$ 之间的点都访问了一遍，那么他所需的时间为：（自己画个图就能明白了~~其实是我懒得画图了~~） $s_j-s_i+dis_i+dis_j 也许有人还有问题，如何保证叶子结点的顺序呢？ 题目中有一句话：“本质上，题目给出的树就是住址构成的 字典树/Trie树 ”。 这就保证了按照读入的顺序跑一遍 $DFS$ 依次访问到的是编号从大到小的叶子结点(因为链式前向星是倒序遍历的，不过正倒并不影响)。 我在程序另开一个数组 $st$ 其中 $st_i$ 表示从大到小第i个叶子结点的编号： 设叶子结点为 $m$ (实际上最多为 $n-1$ )，值域为 $w$， 总复杂度为 $O(k*log(w)*log(m))

下面是我的代码：仅供参考，略有压行，大佬不喜勿喷

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
struct EDGE{int to,next;ll w;} e[maxn<<1];
bool nl[maxn];//not leaf 
int n,m,k,root,cnt,dep[maxn],fa[maxn][22],Log2[maxn],head[maxn];
ll dis[maxn],s[maxn];
void add(int u,int v,ll w)
{e[++cnt].to=v;e[cnt].w=w;e[cnt].next=head[u];head[u]=cnt;}
inline void dfs(int u,int f)
{
    dep[u]=dep[f]+1;fa[u][0]=f;
    for(int i=1;(1<<i)<=dep[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u];i;i=e[i].next) {
        if(e[i].to!=f) nl[u]=1,
            dis[e[i].to]=dis[u]+e[i].w,dfs(e[i].to,u);
    }
}
inline int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=fa[x][Log2[dep[x]-dep[y]]-1];
    if(x==y) return x;
    for(int k=Log2[dep[x]]-1;k>=0;k--) if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
    return fa[x][0];
}
int st[maxn],tot;//st[]:存叶子几点的编号 
inline void DFS(int u)//找到所有叶子结点 
{
    for(int i=head[u];i;i=e[i].next) 
        if(e[i].to!=fa[u][0]) DFS(e[i].to);
    if(!nl[u]) st[++tot]=u;
}
inline ll calc(int u,int v) {return s[v]+dis[st[v]]-s[u]+dis[st[u]];}
inline int erfen(int s,ll x)//对能走到的位置二分 
{
    int L=s,R=tot,res=s-1;
    while(L<=R) {
        int mid=(L+R)>>1;
        if(calc(s,mid)<=x) res=mid,L=mid+1;
        else R=mid-1;
    }
    return res;
}
inline bool check(ll x)
{
    int last=0,temp=0;
    for(int i=1;i<=k;i++) {
        temp=erfen(last+1,x);
        if(temp==last) return 0;
        if(temp>=tot) return 1;
        last=temp;
    }
    return temp==tot;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1,x,y,w;i<n;i++) {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);add(y,x,w);
    }
    dfs(1,0);DFS(1);
    for(int i=1;i<=n;i++) Log2[i]=Log2[i-1]+(1<<Log2[i-1]==i);
    for(int i=2;i<=tot;i++) //求解s数组 
        s[i]=s[i-1]+dis[st[i]]+dis[st[i-1]]-dis[LCA(st[i-1],st[i])]*2LL;
    ll l=1,r=1LL<<60,ans=1LL<<60;
    while(l<=r) {//对答案二分 
        ll mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}

代码中有些小细节还需特别注意， 总的来说是一道很不错的二分答案的题目