请求大佬指教:60pts求助
查看原帖
请求大佬指教:60pts求助
38171
DeNeRATe楼主2020/8/27 21:03
//P1084
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define LL long long
#define Lowbit(X) (X&(-X))
#define Lson (X<<1)
#define Rson (X<<1|1)
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define FOR_SIDE(i,A) for(LL i=Head[A];i;i=Next[i])
#define INF 0x7fffffff
using namespace std;
const LL MAXN=5e4+10;

LL Total,u,v,w,Test;
LL L,R,Ans,Cnta,Cntb,Pos;
LL Arm[MAXN],Loc[MAXN];
LL Anc[MAXN][20],Dist[MAXN][20];
LL Next[MAXN<<1],Head[MAXN],End[MAXN<<1],Cur,Val[MAXN<<1];
struct Node {
    LL Time,ID;
    friend bool operator < (Node X,Node Y)
    { return X.Time<Y.Time; }
}A[MAXN],B[MAXN];
bool Vis[MAXN],Jud,Mine[MAXN],In[MAXN];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Add_Edge(LL From,LL To,LL Temp) {
    Next[++Cur]=Head[From];
    Head[From]=Cur;
    End[Cur]=To;
    Val[Cur]=Temp;
}

inline void Init(LL New,LL Pre,LL Len) {
    Anc[New][0]=Pre;
    Dist[New][0]=Len;
    FOR(i,1,18) {
        Anc[New][i]=Anc[Anc[New][i-1]][i-1];
        Dist[New][i]=Dist[New][i-1]+Dist[Anc[New][i-1]][i-1];
    }
    FOR_SIDE(i,New) {
        if(End[i]==Pre) continue;
        R+=Val[i];
        Init(End[i],New,Val[i]);
    }
}

inline void Up(LL New,LL Limit) {
    LL Len=0;
    BOR(i,18,0) if(Anc[New][i]>1 && Dist[New][i]+Len<=Limit) 
        New=Anc[New][i],Len+=Dist[New][i];
    if(Anc[New][0]==1 && Len+Dist[New][0]<=Limit) 
        A[++Cnta]=Node{ Limit-(Len+Dist[New][0]),New };
    else Vis[New]=true;
}

inline bool Check_two(LL New,LL Pre) {
    bool Flag=true,Have=false;
    if(Vis[New]) return true;
    FOR_SIDE(i,New) {
        if(End[i]==Pre) continue;
        Have=true;
        if(!Check_two(End[i],New)) {
            Flag=false;
            if(New==1) B[++Cntb]=Node{ Val[i],End[i] },In[End[i]]=true,Loc[End[i]]=Cntb;
            else return false;
        }
    }
    if(!Have) return false;
    else return Flag;
}

inline bool Solve() {
    sort(A+1,A+Cnta+1);
    sort(B+1,B+Cntb+1);
    if(Cnta<Cntb) return false;
    FOR(i,1,Cnta) {
    	if(In[A[i].ID] && B[Loc[A[i].ID]].Time>A[i].Time && !Mine[Loc[A[i].ID]]) {
        	Mine[Loc[A[i].ID]]=true; continue;
        }
        if(B[Pos].Time<=A[i].Time) {
        	Mine[Pos++]=true;
        	while(Mine[Pos]) Pos++;
        }
        if(Pos>Cntb) return true;
    }
    FOR(i,1,Cntb) if(!Mine[i]) return false;
    return true;
}

inline void Clean() {
	Cl(In,false); Cl(Vis,false); Cl(Mine,false);
	Cl(A,0); Cl(B,0); Cnta=0; Cntb=0; 
	Cl(Loc,0); Pos=1;
} 

inline bool Check_one(LL Temp) {
    Clean();
    FOR(i,1,Test) Up(Arm[i],Temp);
    if(Check_two(1,0)) return true;
    if(Solve()) return true;
    else return false;
}

int main() {
    //File();
    scanf("%lld",&Total);
    FOR(i,1,Total-1) {
        scanf("%lld %lld %lld",&u,&v,&w);
        Add_Edge(u,v,w); Add_Edge(v,u,w);
    }
    Init(1,0,0);
    scanf("%lld",&Test);
    FOR(i,1,Test) scanf("%lld",&Arm[i]);
    while(L<=R) {
        LL Mid=(L+R)>>1;
        if(Check_one(Mid)) R=Mid-1,Jud=true,Ans=Mid;
        else L=Mid+1;
    }
    if(Jud) printf("%lld\n",Ans);
    else printf("-1\n");
    //fclose(stdin); fclose(stdout);
    system("pause");
    return 0;
}
2020/8/27 21:03
加载中...