其实在很久之前我就差不多大致理解思路

但由于过于蒟蒻

难以实现

 

在大约一月前我刷树形dp时，又刷到这道题

嗯，我用dp get到0pts的好成绩

 

反正我现在就是懂了

#include
     
      #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
      
       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
       
        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
        
         >1;        if(check(mid))r=mid-1;        else l=mid+1;    }        printf("%lld",l);    re 0;}