题面

题解

为啥一直莫名其妙\(90\)分啊……重构了一下代码才\(A\)掉……

先考虑直接\(dp\)怎么做

树形\(dp\)的时候，记一下断开某个节点的最小值，就是从根节点到它的路径上最短的边长，预处理的时候就可以搞出来。然后如果一个节点和根断开了，那么它儿子里所有点都会和根断开

然后是关于虚树的构建……我直接把\(attack\)大佬的博客里说的贴过来好了

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R ll x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=5e5+5;struct eg{int v,nx,w;}e[N<<1];int head[N],tot;inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;}vector
      
       to[N];inline void add_edge(R int u,R int v){to[u].push_back(v);}int dfn[N],top[N],fa[N],dep[N],sz[N],son[N],q[N],a[N];ll mn[N];int n,m,cnt,t;void dfs1(int u){    sz[u]=1,dep[u]=dep[fa[u]]+1;    go(u)if(v!=fa[u]){        fa[v]=u,mn[v]=min(mn[u],1ll*e[i].w),dfs1(v),sz[u]+=sz[v];        sz[v]>sz[son[u]]?son[u]=v:0;    }}void dfs2(int u,int t){    top[u]=t,dfn[u]=++cnt;    if(!son[u])return;    dfs2(son[u],t);    go(u)if(!top[v])dfs2(v,v);}int LCA(int u,int v){    while(top[u]!=top[v]){        dep[top[u]]
       
        =dfn[lca])add_edge(q[t-1],q[t]),--t;    lca!=q[t]?(add_edge(lca,q[t]),q[t]=lca):0;    q[++t]=u;}ll dp(int u){    if(to[u].empty())return mn[u];    ll res=0;    fp(i,0,to[u].size()-1)res+=dp(to[u][i]);    vector
        
         ().swap(to[u]);    return min(1ll*mn[u],res);}inline bool cmp(const int &x,const int &y){return dfn[x]