思路

虚树上DP

虚树相当于一颗包含了所有询问的关键点信息的树，包含的所有点只有询问点和它们的LCA，所以点数是\(2k\)级别的，这样的话复杂度就是\(O(\sum k)\)，复杂度就对了

虚树重点就是虚树的构造

用栈可以进行虚树的构造

过程如下

设现在加入点u

如果栈为空或只有一个元素，直接加入即可（延长当前链）

如果LCA(u,S[top])=S[top]，把u加入即可（延长树链）

否则证明u和S中的树链在lca的两个子树中，在dfn[lca]<=dfn[S[top-1]]的条件下，从S[top-1]向S[top]连边，然后弹出

如果最后lca=S[top]，证明这颗子树构造完成，加入u即可

否则证明lca在S[top-1]和S[top]之间，从lca向S[top]连边，然后pop出S[top]，lca入栈

最后把u加入即可

这题建出虚树之后就直接DP就好了

如果u不是关键点

\(DP[u]=\sum_{v\in son[u]} min(minx[v],DP[v])\)

如果u是关键点

\(DP[u]=minx[u]\)

minx[u]是断开1到u路径的最小代价

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define int long longusing namespace std;const int MAXN = 250010;int n,m;struct Graph{    vector
         
           to[MAXN],wx[MAXN]; void addedge(int ui,int vi,int wi){ to[ui].push_back(vi); wx[ui].push_back(wi); }}G1,G2;int S[MAXN],topx,dfn[MAXN],dfs_clock,fa[MAXN][20],dep[MAXN],minx[MAXN],mark[MAXN];void dfs1(int u,int f){ dep[u]=dep[f]+1; dfn[u]=++dfs_clock; fa[u][0]=f; for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int i=0;i
          
           =0;i--) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=19;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0];}bool cmp(int a,int b){ return dfn[a]
           
            1&&dfn[Lca]<=dfn[S[topx-1]]){ G2.addedge(S[topx-1],S[topx],0); topx--; } if(Lca!=S[topx]){ G2.addedge(Lca,S[topx],0); S[topx]=Lca; } S[++topx]=u;}int dfs2(int u){ int ans=0; for(int i=0;i