3.4Code

#include<algorithm>
#include<iostream>
#include<cstdio>
#define inf 0x3f3f3f3f
#define N 500005
#define root true
using namespace std; typedef pair<int ,int > Pair; struct Edge{
int v,c,nxt;
}e[N<<1];
int head[N],tot; void AddEdge(int u,int v,int c){
e[++tot]=(Edge){v,c,head[u]};head[u]=tot;
e[++tot]=(Edge){u,c,head[v]};head[v]=tot;
} int k;
int n,m;
int dep[N];
int pos[N];
Pair other[N];
int f[N][20]; int dfs(int u,int fa){
f[u][0]=fa;dep[u]=dep[fa]+1;
for(int i=head[u];i;i=e[i].nxt)
if(e[i].to!=fa){
dfs(e[i].to,u);
d[e[i].to]=d[u]+e[i].c;
}
} int DFS(int u){
if();
} Pair depth(int pos,int tim){
for(int i=20;i>-1;--i)
if(f[pos][i]&&tim>(d[pos]-d[f[pos][i]-1]))
tim-=d[pos]-d[f[pos][i]-1],pos=f[pos][i];
return make_pair(pos,tim);
} queue<Pair>que; bool check(int ans){
que.clear();
for(int i=1;i<=m;++i){
other[i]=depth(pos[i],ans);
if(other[i].first==root)
que.push(other[i]);
}
DFS(1);
} int main(){
scanf("%d",&n);int a,b,c;
for(int i=1;i<n;++i){
scanf("%d%d%d",&a,&b,&c);
AddEdge(a,b,c);
}
dfs(1,0);
for(int i=1;i<=20;++i)
for(int j=1;j<=n;++j)
fa[j][i]=fa[fa[j][i-1]][i-1];
scanf("%d",&m);
for(int i=1;i<=n;++i)
scanf("%d",pos[i]);
int l=1,r=inf,mid;
while(l<r){
mid=(l+r)>>1;
if(check(mid))
r=mid-1;
else l=mid+1;
}
return 0;
}
上一篇:有意思的bug


下一篇:Java后端工程师必备书单(含大后端方向相关书籍)