关于在根的儿子原地驻扎
查看原帖
关于在根的儿子原地驻扎
925506
ACRUSHj楼主2023/7/24 22:55

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;
}

record

代码似乎带了三只 log

2023/7/24 22:55
加载中...