rt,感觉是处理了,但没起效果,求助
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
struct edge{
int to,w;
bool operator<(const edge& x)const{return w<x.w;}
};
int n,m,a[N],f[N][17],d[N][17],dep[N],h[N];
bool b[N];
vector<edge>e[N];
multiset<edge>p,q;multiset<edge>::iterator it;
void dfs(int u){
dep[u]=dep[f[u][0]]+1;
for(int i=1;i<=16;i++)f[u][i]=f[f[u][i-1]][i-1];
for(int i=1;i<=16;i++)d[u][i]=d[u][i-1]+d[f[u][i-1]][i-1];
for(auto x:e[u]){
int v=x.to,l=x.w;
if(v!=f[u][0])f[v][0]=u,d[v][0]=l,dfs(v);
}
return;
}
bool DFS(int u){
if(e[u].empty())return 1;
bool flag=1;
for(auto x:e[u]){
int v=x.to;
if(v!=f[u][0]&&!b[v])flag=flag&&DFS(v);
}
return flag;
}
bool check(int tim){
q.clear();p.clear();
for(int i=1;i<=n;i++)h[i]=1e9,b[i]=0;
for(int i=1;i<=m;i++){
int k=a[i],dis=0;
for(int j=16;j>=0;j--)
if(f[k][j]>1&&dis+d[k][j]<=tim)dis+=d[k][j],k=f[k][j];
if(f[k][0]==1&&dis+d[k][0]<tim)q.insert({k,tim-dis-d[k][0]}),h[k]=min(h[k],tim-dis-d[k][0]);
else b[k]=1;
}
for(auto x:e[1])if(!b[x.to]&&DFS(x.to))p.insert({x.to,x.w});
if(q.size()<p.size())return 0;
for(auto u:p){
it=q.lower_bound(u);
if(it==q.end()&&h[u.to]==(int)1e9)return 0;
if(it==q.end())q.erase(q.find({u.to,h[u.to]})),h[u.to]=1e9;
else q.erase(it);
}
return 1;
}
int Search(int l,int r){
if(l>=r)return l;
int mid=l+r>>1;
if(check(mid))return Search(l,mid);
else return Search(mid+1,r);
}
signed main(){
//freopen("flu.in","r",stdin);
//freopen("flu.out","w",stdout);
scanf("%d",&n);
for(int i=1,x,y,z;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
e[x].push_back({y,z});e[y].push_back({x,z});
}
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%d",&a[i]);
dfs(1);
if(!check(1e9))puts("-1");
else printf("%d\n",Search(1,1e9));
system("pause");
return 0;
}
代码似乎带了三只 log