给一颗树，树边带权，有一些标记了的点，每个点可以在树上沿边移动，移动代价为边权。求一种移动策略，使得移动之后的树从根节点到每个叶子都至少有一个标记点，且每个点移动代价的最大值最小。最终状态下根节点不能带标记，无解输出-1
最值问题，且问题有单调性，可以二分，设当前要check的最大值为x，那么每个点都可以移动x
对于一个带了标记的点来说，它的子树中的叶子都是满足条件的，如果把这个点向上移动，它能覆盖到的叶子只会多不会少，所以采用贪心策略，将每个点向上移动x，向上跳的过程可以用倍增完成，接下来分为两种情况（设跳到的点为i）：
①跳了x之后未到根。即i !=1，此时直接给i点打上标记，表示跳到这个点，这个是较简单的情况
②跳了x之后到了根。那么此时可以消耗的代价还有剩的，那么它可以从根节点走向其它的未标记点
记录一下这个点到1的过程中经过的1的儿子节点（即depth==2的点），设它为j，对所有可以到1的标记点按照剩余代价从小到大排序，从小到大枚举，对于一个标记点，如果它的剩余代价小于dis(1,j)且j未被标记，那么就将它移动到j点，因为如果移动其它点的话会消耗dis(1,j)的代价，但是移动它只会消耗剩余代价，而剩余代价小于dis(1,j)，所以血赚不亏
处理好j->1->j这种情况后，所有的点都当成是从1出发向某一个点，不考虑返回的情况，即使它就是从j->1->j。这就很简单了，对所有未标记的点到1的距离从大到小排序，对剩余代价大小从大到小排序，大的对应大的即可
P.S.标记可以从儿子向父亲转移，即如果一个点的所有儿子都带有标记，它也会带标记
Code：
#include<bits/stdc++.h> #define N 50005 typedef long long ll; const int temp=19; const ll INF = 10000000000000000; using namespace std; int n,m; int fa[N][temp],dep[N],r[N]; ll dis[N][temp]; vector< pair<ll,int> > rest; vector<ll> ret,q; bool v[N]; //当前点的军队还可以走的路 struct Edge { int next,to; ll dis; }edge[N<<1];int head[N],cnt=1; void add_edge(int from,int to,ll dis) { edge[++cnt].next=head[from]; edge[cnt].to=to; edge[cnt].dis=dis; head[from]=cnt; } template <class T> void read(T &x) { char c;int sign=1; while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48; while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign; } void dfs(int rt) { dep[rt]=dep[fa[rt][0]]+1; for(int i=head[rt];i;i=edge[i].next) { int to=edge[i].to; if(to==fa[rt][0]) continue; fa[to][0]=rt; dis[to][0]=edge[i].dis; for(int i=1;i<temp;++i) fa[to][i]=fa[fa[to][i-1]][i-1]; for(int i=1;i<temp;++i) dis[to][i]=dis[to][i-1]+dis[fa[to][i-1]][i-1]; dfs(to); } } void DFS(int rt)//收束 { bool flag=1,son=0; for(int i=head[rt];i;i=edge[i].next) { int to=edge[i].to; if(to==fa[rt][0]) continue; son=1; DFS(to); flag&=v[to]; } if(!son) flag=0; v[rt]|=flag; } bool cmp(ll a,ll b) {return a>b;} bool check(ll x)//每个军队可以走x { rest.clear(); ret.clear(); q.clear(); memset(v,0,sizeof(v)); for(int i=1;i<=m;++i) { int now=r[i];//对now进行倍增，最多跳到dep==2 ll res=x; for(int j=temp-1;j>=0;--j) { if(dep[fa[now][j]]>=2&&res>=dis[now][j]) { res-=dis[now][j]; now=fa[now][j]; } } if(dep[now]!=2||res<dis[now][0]) v[now]=1; else rest.push_back(make_pair(res-dis[now][0],now)); } DFS(1); sort(rest.begin(),rest.end()); for(int i=0;i<(int)rest.size();++i) { ll d=rest[i].first; int to=rest[i].second; if(d<dis[to][0]&&!v[to]) v[to]=1; else ret.push_back(d); } sort(ret.begin(),ret.end(),cmp); for(int i=head[1];i;i=edge[i].next) { int to=edge[i].to; if(!v[to]) q.push_back(edge[i].dis); } sort(q.begin(),q.end(),cmp); if((int)ret.size()<(int)q.size()) return false; for(int i=0;i<(int)q.size();++i) { if(ret[i]<q[i]) return false; } return true; } int main() { read(n); for(int i=1;i<n;++i) { int x,y; ll z; read(x);read(y);read(z); add_edge(x,y,z); add_edge(y,x,z); } dfs(1); read(m); for(int i=1;i<=m;++i) read(r[i]); ll l=0,r=INF,ans=-1; while(l<=r) { ll mid=(l+r)>>1; if(check(mid)) ans=mid,r=mid-1; else l=mid+1; } cout<<ans<<endl; return 0; }转载于:https://www.cnblogs.com/Chtholly/p/11370220.html
