Description
\(H\) 国有 $n $ 个城市，这 \(n\) 个城市用 $ n-1 $ 条双向道路相互连通构成一棵树，$1 $ 号城市是首都，也是树中的根节点。
$H $国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。
现在，在 \(H\) 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。
请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。
Solution
二分答案，考虑如何检验
下面将根的邻居称为次根，所对应的子树称为次根子树
对每个军队，用树上倍增暴力上移，但最多移到次根
将所有现在在次根上，并且有能力到达根的军队称为强军，到达根后还剩下的时间称为余量，否则称为弱军
DFS 一遍，检查弱军是否能*每个次根子树
对于每个不能被弱军*的子树，考虑该子树内是否有强军，如果有则用掉一个余量最小的强军并完成这个子树（但是如果老小能够到根再回来，则不直接用，仍然将其投入市场），否则将其加入待处理次根子树中，参数为 \(dis[p]\)
对于每个未被用掉的强军，加入可用军中，参数为 \(rest[p]\)
将可用军和待处理次根子树贪心匹配即可
下面描述一下算法流程
- 倍增上移
- 扫描所有军队，找出强军并做标记 \(strong[i]\)，同时计算其余量 \(rest[i]\)
- DFS，检查每个次根子树是否被弱军*
- 处理每个不能被弱军*的子树，若自己有强军则用掉强军（但是如果老小能够到根再回来，则不直接用，仍然将其投入市场），否则，生成待处理子树集合，参数为 \(dis\)；生成可用军集合，参数为 \(rest\)
- 可用军和待处理次根子树贪心匹配
（又自闭了一早上）
一组可能有用的 hack 数据
7
2 1 2
3 1 3
4 3 1
5 3 2
6 1 1
7 4 1
4
3 5 6 7
ans = 4
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200005;
const int lgn = 21;
int n,m,t1,t2,t3,fa[N][lgn],dis[N],pos[N],vis[N];
vector <pair<int,int> > g[N];
void printvec(string s,vector<int> vec)
{
cout<<s<<" ";
for(int i:vec) cout<<i<<", ";
cout<<endl;
}
void input()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<n;i++)
{
cin>>t1>>t2>>t3;
g[t1].push_back({t2,t3});
g[t2].push_back({t1,t3});
}
cin>>m;
for(int i=1;i<=m;i++) cin>>pos[i];
}
void dfs1(int p)
{
vis[p]=1;
for(pair<int,int> pr:g[p])
{
int q=pr.first, w=pr.second;
if(vis[q]==0)
{
dis[q]=dis[p]+w;
fa[q][0]=p;
dfs1(q);
}
}
}
void presolve()
{
dfs1(1);
fa[1][0]=1;
for(int i=1;i<lgn;i++)
{
for(int j=1;j<=n;j++)
{
fa[j][i]=fa[fa[j][i-1]][i-1];
}
}
memset(vis,0,sizeof vis);
}
namespace checker
{
int vis[N],pos[N],tim[N],rest[N],strong[N],subroot[N],haveweak[N];
vector <int> svec[N],lst,ss;
void init(int T)
{
memset(vis,0,sizeof vis);
memset(pos,0,sizeof pos);
memset(tim,0,sizeof tim);
memset(rest,0,sizeof rest);
memset(strong,0,sizeof strong);
memset(subroot,0,sizeof subroot);
memset(haveweak,0,sizeof haveweak);
for(int i=1;i<=n;i++)
{
svec[i].clear();
}
lst.clear();
ss.clear();
for(pair<int,int> pr:g[1])
{
int q=pr.first;
subroot[q]=1;
}
for(int i=1;i<=n;i++) pos[i]=::pos[i], tim[i]=T;
}
void jmp(int p)
{
for(int i=lgn-1;i>=0;--i)
{
if(fa[pos[p]][i]>1 && dis[pos[p]]-dis[fa[pos[p]][i]]<=tim[p])
{
tim[p]-=dis[pos[p]]-dis[fa[pos[p]][i]];
pos[p]=fa[pos[p]][i];
}
}
}
void chkstrong(int p)
{
if(subroot[pos[p]] && tim[p]>=dis[pos[p]])
{
rest[p]=tim[p]-dis[pos[p]];
strong[p]=1;
}
}
int fg;
void dfs2(int p)
{
vis[p]=1;
if(haveweak[p]) return;
int u=0;
for(pair<int,int> pr:g[p])
{
int q=pr.first, w=pr.second;
if(!vis[q])
{
u=1;
dfs2(q);
}
}
if(u==0)
{
fg=0;
}
}
bool check(int T)
{
//cout<<"checking "<<T<<endl;
init(T);
for(int i=1;i<=m;i++) jmp(i);
for(int i=1;i<=m;i++) chkstrong(i);
for(int i=1;i<=m;i++)
{
if(!strong[i])
{
haveweak[pos[i]]=1;
}
else
{
svec[pos[i]].push_back(rest[i]);
}
}
int mxs=0;
for(int i=1;i<=n;i++)
{
sort(svec[i].begin(),svec[i].end());
reverse(svec[i].begin(),svec[i].end());
mxs=max(mxs,(int)(svec[i].size()));
}
//cout<<mxs<<endl;
vis[1]=1;
for(int i=1;i<=n;i++)
{
if(subroot[i])
{
fg=1;
dfs2(i);
if(!fg)
{
if(svec[i].size() && svec[i].back()<dis[i])
{
svec[i].pop_back();
}
else
{
lst.push_back(dis[i]);
}
}
}
}
for(int i=1;i<=n;i++)
{
for(int p:svec[i])
{
ss.push_back(p);
}
}
sort(ss.begin(),ss.end());
sort(lst.begin(),lst.end());
//printvec("ss: ",ss);
//printvec("lst: ",lst);
multiset <int> sss;
for(int p:ss) sss.insert(p);
for(int p:lst)
{
auto it=sss.lower_bound(p);
if(it==sss.end())
{
return 0;
}
else
{
sss.erase(it);
}
}
return 1;
}
}
using checker::check;
signed main()
{
//freopen("p1084.in","r",stdin);
//freopen("p1084.out","w",stdout);
input();
presolve();
int l=0,r=1e14;
while(l<r)
{
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r<<endl;
}
一个可能有用的数据生成器
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
#define random(a, b) rand()%(b-a+1) + a
int cnt=0;
void test()
{
ofstream fin("p1084.in",ios::out);
int n=7,m=4;
fin<<n<<endl;
for(int i=2;i<=n;i++)
{
fin<<i<<" "<<random(1,i-1)<<" "<<random(1,3)<<endl;
}
fin<<m<<endl;
for(int i=1;i<=m;i++)
{
fin<<random(2,n)<<" ";
}
fin<<endl;
fin.close();
cout<<" testing "<<endl;
system("p1084.exe");
cout<<" generating ans"<<endl;
system("tmp2.exe");
cout<<" comparing"<<endl;
ifstream fout("p1084.out",ios::in);
int aout;
fout>>aout;
fout.close();
ifstream fans("p1084.ans",ios::in);
int aans;
fans>>aans;
fans.close();
++cnt;
if(aans==aout)
{
cout<<"Test #"<<cnt<<" Passed"<<endl;
}
else
{
cout<<"Failed test #"<<cnt<<endl;
cout<<" output = "<<aout<<" answer = "<<aans<<endl;
system("pause");
}
}
signed main()
{
while(true)
{
test();
}
}