其实在很久之前我就差不多大致理解思路
但由于过于蒟蒻
难以实现
在大约一月前我刷树形dp时，又刷到这道题
嗯，我用dp get到0pts的好成绩
反正我现在就是懂了
#include<bits/stdc++.h> #define re return #define ll long long #define dec(i,l,r) for(register int i=l;i>=r;--i) #define inc(i,l,r) for(register int i=l;i<=r;++i) using namespace std; template<typename T>inline void rd(T&x) { char c;bool f=0; while((c=getchar())<'0'||c>'9')if(c=='-')f=1; x=c^48; while((c=getchar())>='0'&&c<='9')x=x*10+(c^48); if(f)x=-x; } const int maxn=300005; int cnt,k,n,m,hd[maxn],fa[maxn][21]; int size1,pos[maxn],vis[maxn]; long long dis[maxn][21]; struct node{ int to,nt,val; }e[maxn<<1]; inline void add(int x,int y,int z) { e[++k].to=y;e[k].nt=hd[x];hd[x]=k;e[k].val=z; e[++k].to=x;e[k].nt=hd[y];hd[y]=k;e[k].val=z; } inline void dfs(int x) { for(int i=0;fa[fa[x][i]][i];++i) { fa[x][i+1]=fa[fa[x][i]][i]; dis[x][i+1]=dis[x][i]+dis[fa[x][i]][i]; } for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to; if(v==fa[x][0])continue; fa[v][0]=x; dis[v][0]=e[i].val; dfs(v); } } struct lll { int fr,left_dis,id; bool operator<(lll c)const { re left_dis<c.left_dis; } }a[maxn]; int cnta,cntb,need[maxn]; struct lli { int val,id; bool operator<(lli c)const { re val<c.val; } }b[maxn]; inline bool dfs1(int x) { if(vis[x])re 1; int siz=0; for(int i=hd[x];i;i=e[i].nt) { int v=e[i].to; if(v==fa[x][0])continue; siz|=1; if(dfs1(v)==0) {vis[x]=0;re 0;} } if(!siz) {vis[x]=0;re 0;} vis[x]=1; re 1; } inline bool check(ll x) { cntb=cnta=0; inc(i,0,n)vis[i]=0; inc(i,1,m) { int v=pos[i],now=0; dec(i,20,0)if(fa[v][i]>1&&dis[v][i]+now<=x){now+=dis[v][i];v=fa[v][i];} int left=x-now-dis[v][0]; if(fa[v][0]==1&&left>=0) //在边界点//能返回点或者已被注扎 //left是从1出发能走的最远距离 a[++cnta]=(lll){v,left,cnta}; else vis[v]=1; } //将不能被封闭的点标记 for(int i=hd[1];i;i=e[i].nt) { int v=e[i].to; dfs1(v); } sort(a+1,a+cnta+1); int nowa=0; //找到最小的不能返回出发节点（未封闭）的值 inc(i,1,cnta) { if(!vis[a[i].fr]&&a[i].left_dis<dis[a[i].fr][0]) { a[i].left_dis=-1; vis[a[i].fr]=1; --nowa; } } sort(a+1,a+cnta+1); for(int i=hd[1];i;i=e[i].nt) { int v=e[i].to; if(!vis[v])b[++cntb]=(lli){e[i].val,v}; } sort(b+1,b+cntb+1); int nowb=1; inc(i,nowa+1,cnta) { if(b[nowb].val<=a[i].left_dis)++nowb; if(nowb==cntb+1)re 1; } re 0; } int main() { freopen("in.txt","r",stdin); // freopen("testdata.in","r",stdin); int x,y,z; ll l=0,r=0; rd(n); inc(i,2,n) { rd(x),rd(y),rd(z); add(x,y,z); r+=z; } //dfs得到倍增数组 for(int i=hd[1];i;i=e[i].nt) { ++size1; int v=e[i].to; fa[v][0]=1;dis[v][0]=e[i].val; dfs(v); } rd(m); if(m<size1){printf("-1");re 0;} inc(i,1,m)rd(pos[i]); while(l<=r) { int mid=(l+r)>>1; if(check(mid))r=mid-1; else l=mid+1; } printf("%lld",l); re 0; }