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;

}
巴特西

3.4Code

最新文章

热门文章
