不想倍增?数据结构来凑!
答案具有单调性可以二分。
限制了答案后,有一个显然的贪心:在时间允许条件下,一支军队的驻扎点越靠上越优(封锁的点越多)。
那么尽可能把军队往上提。
不搞倍增,直接暴力向上合并。
维护所有位于当前节点的军队以及它们已耗费的时间。
把每个儿子的军队提上来,并给里面的军队时间都加上边权。
然后删掉耗费时间大于当前答案的军队。
于是需要一种支持快速合并、删除大于某个数的元素、整体加的数据结构。
左偏树(可并堆)!
还有一个问题在于根节点不能驻扎。对于根节点不能封锁的儿子,需要将其他儿子剩余的军队移动过来。维护所有需要军队的儿子的边权,和剩余军队的到根节点耗费的时间。双指针扫一遍,把前者较大的和后者较小的匹配检验是否可行。
ちょっと待って。。。好像忽略了一种情况:
(懒得画图了)设需要军队的点为$x$,$y$有一支剩余军队,$z$节点驻扎着一支军队且没有剩余。
可能存在把$z$的军队调往$x$驻扎,$y$的军队调往$z$驻扎满足答案,而直接把$y$的军队调往$x$驻扎不满足的情况。
用已耗费时间衡量军队的优劣的话,这种情况实际上就是把较优的$z$的军队用较劣的$y$的军队“置换”出来。
用$multiset$处理一波,把劣的军队置换出优的军队再检验。还要维护每个点是否有必要驻扎军队,必要的话就把最劣的军队留下。
时间复杂度$O(n\log n\log \sum w)$。
代码:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#define maxn 50005
const long long inf = 1e18;
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
#define ls(x) ls[x]
#define rs(x) rs[x]
long long dat[maxn],tag[maxn],ex[maxn],mid;
int in[maxn],h[maxn],root[maxn],ls[maxn],rs[maxn],siz[maxn],deep[maxn],poi[maxn],ar[maxn],cnt,num;
pair<long long,int>ch[maxn];
multiset<long long>s;
bool ok[maxn],mov[maxn];
struct edge{
int pre,to,l;
}e[maxn<<1];
inline void add(int from,int to,int l){
++in[from];
e[++num].pre=h[from],h[from]=num,e[num].to=to,e[num].l=l;
}
inline bool cmp(const pair<long long,int> &x,const pair<long long,int>&y){
if(x.first!=y.first)return x.first>y.first;
return x.second<y.second;
}
inline void update(int node){
deep[node]=deep[rs(node)]+1;
siz[node]=siz[ls(node)]+siz[rs(node)]+1;
}
inline void datadown(int node,int d){
tag[node]+=d,dat[node]+=d;
}
inline void pushdown(int node){
if(ls(node))datadown(ls(node),tag[node]);
if(rs(node))datadown(rs(node),tag[node]);
tag[node]=0;
}
int merge(int x,int y){
if(!x||!y)return x|y;
if(dat[x]<dat[y])swap(x,y);
if(tag[x])pushdown(x);
rs(x)=merge(rs(x),y);
if(deep[ls(x)]<deep[rs(x)])swap(ls(x),rs(x));
update(x);
return x;
}
void push(int &rt,int x){
dat[++cnt]=x,siz[cnt]=deep[cnt]=1;
ls(cnt)=rs(cnt)=tag[cnt]=0;
rt=merge(rt,cnt);
}
void pop(int &rt){
int l=ls(rt),r=rs(rt);
if(tag[rt])pushdown(rt);
rt=merge(l,r);
}
void dp(int node,int f=1){
ok[node]=mov[node]=in[node]-1;
int x,s;
for(register int i=h[node];i;i=e[i].pre){
x=e[i].to;
if(x==f)continue;
dp(x,node),datadown(root[x],e[i].l);
root[node]=merge(root[node],root[x]);
if(root[node]&&dat[root[node]]<=mid)mov[node]=0;
while(root[node]&&dat[root[node]]>mid)pop(root[node]);
mov[node]&=ok[x],ok[node]&=ok[x];
}
while(root[node]&&dat[root[node]]>mid)pop(root[node]);
ok[node]|=root[node];
}
inline multiset<long long>::iterator pre(int d){
multiset<long long>::iterator ans=s.lower_bound(d);
if(ans==s.end())return --ans;
if(*ans==d)return ans;
return --ans;
}
int main(){
int n=read(),l1,l2,l3,x;
long long l=0,r=0;
multiset<long long>::iterator iter;
for(register int i=1,y,z;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z),r+=z;
int m=read();
for(register int i=1;i<=m;++i)ar[i]=read();
if(in[1]>m){puts("-1");return 0;}
while(l<r){
mid=l+r>>1,l1=l2=l3=0,cnt=0;
s.clear(),s.insert(-inf);
for(register int i=1;i<=n;++i)root[i]=0;
for(register int i=1;i<=m;++i){
if(ar[i]==1)ch[++l3]=make_pair(0,0);
else push(root[ar[i]],0);
}
for(register int i=h[1];i;i=e[i].pre){
x=e[i].to,dp(x);
if(!ok[x])poi[++l1]=e[i].l;
if(root[x])ch[++l3]=make_pair(dat[root[x]]+e[i].l,mov[x]?0:e[i].l),pop(root[x]);
while(root[x])ch[++l3]=make_pair(dat[root[x]]+e[i].l,0),pop(root[x]);
}
sort(ch+1,ch+1+l3,cmp);
for(register int i=1;i<=l3;++i){
if(!ch[i].second)s.insert(ch[i].first);
else {
iter=pre(mid-ch[i].second);
if(*iter==-inf)continue;
s.erase(iter);
s.insert(ch[i].first);
}
}
for(iter=s.begin();iter!=s.end();++iter)ex[++l2]=*iter;
reverse(ex+1,ex+1+l2),--l2;
sort(poi+1,poi+1+l1);
while(l1&&l2&&ex[l2]+poi[l1]<=mid)--l1,--l2;
if(l1)l=mid+1;
else r=mid;
}
printf("%lld\n",l);
}