P1045 · OFFICIAL SOLUTION

P1045 战争游戏官方题解

Gioush OJ · P1045 战争游戏

战争游戏

【题意简述】

给出一棵以 $1$ 为根的带权树以及若干名特工的初始位置。特工可以同时移动，但不能潜伏在根结点。要求每条根到叶子的路径上最终至少有一名特工，求最短时间；无解时输出 Pity!。

【Hint】

【提示】

二分时间。无法到达根的特工尽量向上移动并覆盖原子树；能够到达根的特工先处理必须留在原分支的情况，再与未覆盖根分支按剩余时间贪心匹配。

【数据点 1∼101\sim 101∼10】

二分答案后，可以枚举每名特工的潜伏位置；叶子数较少时，也可以把一个结点能够覆盖的叶子集合压成二进制状态，进行集合 DP。这些做法说明固定时间后的判定只包含两部分：特工能否到达某个位置，以及全部叶子路径是否被覆盖。

【数据点 11∼1911\sim 1911∼19】

当根只有一个儿子时，不存在根分支之间的调度。每名特工尽量向上移动，再递归判断子树是否被覆盖即可。

当树为菊花图时，能够到达根的特工只需记录剩余时间。若某名特工回到根后无法再次进入自己的原分支，而这个分支尚未被覆盖，就应先把同分支中剩余时间最小的特工留在原分支。剩余特工与剩余需求分别排序后贪心匹配。

【正解】

答案具有单调性，因此二分时间 $\operatorname{Limit}$ 。倍增预处理每个结点的祖先以及向上移动的距离。

对于每名特工，先在不越过根的条件下尽量向上跳。若它无法到达根，就标记它能够到达的最高结点。它无法进入其他根分支，停在这里能够覆盖尽量大的原子树，所以一定不劣。

定义 $\operatorname{Cover}(u)$ 表示 $u$ 的子树内全部叶子路径是否已经被局部特工截断，则

\operatorname{Cover}(u)=\operatorname{Mark}(u)\lor \left(u\text{ 不是叶子}\land \bigwedge_{v\in\operatorname{son}(u)}\operatorname{Cover}(v)\right).

若 $u$ 被标记，所有经过 $u$ 的路径均已截断；否则必须让每个儿子子树分别被截断。因此这个递推同时具有充分性与必要性。对根的每个儿子分别检查，记录尚未覆盖的分支。

若一名特工能够到达根，记其原根分支为 $r$ ，到达根后的剩余时间为

\operatorname{Rest}=\operatorname{Limit}-\operatorname{dist}(\operatorname{Army},1).

它能够进入根儿子 $v$ ，当且仅当 $\operatorname{Rest}\geq w(1,v)$ 。

不能立即把所有特工投入统一匹配。若分支 $r$ 尚未覆盖，并且来自 $r$ 的最小剩余时间小于 $w(1,r)$ ，就让这名特工留在原分支。若一个可行方案没有这样做，则分支 $r$ 必须由另一名能力更强的特工负责；交换两名特工后，较弱特工留在原分支，较强特工接替原任务，方案仍然可行。

完成预留后，把剩余时间与未覆盖分支的根边权分别从小到大排序。若当前特工不能满足最小需求，它也不能满足后续需求，可以跳过；否则让它负责当前最小需求。交换论证说明这一贪心是充要的。

令 $V$ 为全部边权之和。若时间 $V$ 仍不可行，则问题无解；否则二分得到最小可行时间。

【复杂度分析】

一次判定包含倍增移动、树上覆盖与排序，时间复杂度为 $\mathcal{O}((n+m)\log n)$ 。总时间复杂度为 $\mathcal{O}((n+m)\log n\log V)$ ，空间复杂度为 $\mathcal{O}(n\log n)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/304Name:wargame.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 5001011using namespace std;12int T,n,m,Head[MAXN],Total=0,Fa[MAXN][20],Army[MAXN];13int RootVal[MAXN],MinID[MAXN],NeedVal[MAXN],cn=0,cf=0,cr=0;14long long Value[MAXN][20],SumEdge=0,RestList[MAXN];15bool Mark[MAXN],Need[MAXN],Used[MAXN];16struct edge{17    int St,Ed,Next;18    int Value;19}Edge[MAXN<<1];20struct army{21    long long Rest;22    int Root;23}Free[MAXN];24void Edge_Add(int St,int Ed,int Value){25    Edge[++Total]={St,Ed,Head[St],Value};26    Head[St]=Total;27}28void DFS(int Now,int From){29    for(int i=Head[Now];i;i=Edge[i].Next){30        int To=Edge[i].Ed;31        if(To==From) continue;32        Fa[To][0]=Now;33        Value[To][0]=Edge[i].Value;34        if(Now==1) RootVal[To]=Edge[i].Value;35        DFS(To,Now);36    }37}38bool Cover(int Now,int From){39    if(Mark[Now]) return true;40    bool HasSon=false;41    for(int i=Head[Now];i;i=Edge[i].Next){42        int To=Edge[i].Ed;43        if(To==From) continue;44        HasSon=true;45        if(!Cover(To,Now)) return false;46    }47    return HasSon;48}49bool cmp(army a,army b){return a.Rest<b.Rest;}50bool Judge(long long Limit){51    memset(Mark,0,sizeof(bool)*(n+2));52    memset(Need,0,sizeof(bool)*(n+2));53    memset(Used,0,sizeof(bool)*(m+2));54    memset(MinID,0,sizeof(int)*(n+2));55    cf=cn=cr=0;56    for(int i=1;i<=m;i++){57        int Now=Army[i];58        long long UsedValue=0;59        for(int j=17;j>=0;j--){60            if(Fa[Now][j]>1&&UsedValue+Value[Now][j]<=Limit){61                UsedValue+=Value[Now][j];62                Now=Fa[Now][j];63            }64        }65        if(Fa[Now][0]==1&&UsedValue+Value[Now][0]<=Limit){66            Free[++cf]={Limit-UsedValue-Value[Now][0],Now};67        }68        else Mark[Now]=true;69    }70    for(int i=Head[1];i;i=Edge[i].Next){71        int To=Edge[i].Ed;72        if(!Cover(To,1)) Need[To]=true;73    }74    sort(Free+1,Free+cf+1,cmp);75    for(int i=1;i<=cf;i++){76        int Root=Free[i].Root;77        if(!MinID[Root]) MinID[Root]=i;78    }79    for(int i=Head[1];i;i=Edge[i].Next){80        int To=Edge[i].Ed;81        if(!Need[To]) continue;82        int Pos=MinID[To];83        if(Pos&&Free[Pos].Rest<RootVal[To]){84            Used[Pos]=true;85            Need[To]=false;86        }87    }88    for(int i=Head[1];i;i=Edge[i].Next){89        int To=Edge[i].Ed;90        if(Need[To]) NeedVal[++cn]=RootVal[To];91    }92    for(int i=1;i<=cf;i++){93        if(!Used[i]) RestList[++cr]=Free[i].Rest;94    }95    sort(NeedVal+1,NeedVal+cn+1);96    sort(RestList+1,RestList+cr+1);97    int Pos=1;98    for(int i=1;i<=cr&&Pos<=cn;i++){99        if(RestList[i]>=NeedVal[Pos]) Pos++;100    }101    return Pos>cn;102}103void Solve(){104    scanf("%d%d",&n,&m);105    memset(Head,0,sizeof(int)*(n+2));106    memset(Fa,0,sizeof(Fa[0])*(n+2));107    memset(Value,0,sizeof(Value[0])*(n+2));108    memset(RootVal,0,sizeof(int)*(n+2));109    Total=0;SumEdge=0;110    int In1,In2,In3;111    for(int i=1;i<n;i++){112        scanf("%d%d%d",&In1,&In2,&In3);113        Edge_Add(In1,In2,In3);114        Edge_Add(In2,In1,In3);115        SumEdge+=In3;116    }117    for(int i=1;i<=m;i++) scanf("%d",&Army[i]);118    DFS(1,0);119    for(int j=1;j<=17;j++){120        for(int i=1;i<=n;i++){121            Fa[i][j]=Fa[Fa[i][j-1]][j-1];122            Value[i][j]=Value[i][j-1]+Value[Fa[i][j-1]][j-1];123        }124    }125    if(!Judge(SumEdge)){puts("Pity!");return;}126    long long Left=0,Right=SumEdge;127    while(Left<Right){128        long long Mid=(Left+Right)>>1;129        if(Judge(Mid)) Right=Mid;130        else Left=Mid+1;131    }132    printf("%lld\n",Left);133}134int main(){135    int c;136    scanf("%d%d",&c,&T);137    while(T-->0) Solve();138    return 0;139}