题目大意

给你一棵树和树上的许多条从后代到祖先的链，选择每条链需要一定代价，问覆盖整棵树的所有点的最小代价是多少。

\(n,m\leq 100000\)

---

正解

（由于时间过于久远，所以直接说正解算了）

对于这样的题，显然有一种暴力的DP做法。

设\(f_{i,j}\)表示\(i\)子树全部被覆盖，其中伸出来的一条链到达深度为\(j\)的祖先时的最小代价。

转移不在此赘述。

然后可以线段树优化。

有两种情况：从\(i\)子树伸出来的链是最高的；从\(i\)伸出来的链是最高的。

我们钦定某一条链是最高的，不用管是否存在其他的链高过它的情况，因为如果有那样的情况，那么这个状态的答案就会被覆盖掉。

首先记录一下每个子树的最优答案之和，记作\(sum\)。

枚举子树，对于它的所有状态加上\(sum\)，减去它本身的最优答案。也就是将其它子树的答案之和给它加上。对于自己，就直接用\(sum\)加上所选择的链的代价。

然后线段树合并即可。

---

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define N 300010#define INF 1000000000000000000int n,m;struct EDGE{    int to;    EDGE *las;} e[N*2];int ne;EDGE *last[N];int dep[N];struct EDGE2{    int to,w;    EDGE2 *las;} e2[N*2];int ne2;EDGE2 *last2[N];struct Node{    Node *l,*r;    long long mn,tag;    inline void pushdown(){        l->mn+=tag,l->tag+=tag;        r->mn+=tag,r->tag+=tag;        tag=0;          }    inline void update(){mn=min(l->mn,r->mn);}} d[N*30],*null;int cnt;inline Node *newnode(){return &(d[++cnt]={null,null,INF,0});}Node *root[N];void change(Node *t,int l,int r,int x,long long c){    if (l==r){        t->mn=min(t->mn,c);        return;    }    t->pushdown();    int mid=l+r>>1;    if (x<=mid)        change(t->l==null?t->l=newnode():t->l,l,mid,x,c);    else        change(t->r==null?t->r=newnode():t->r,mid+1,r,x,c);    t->update();}void cut(Node *t,int l,int r,int en){    if (t==null)        return;    t->pushdown();    int mid=l+r>>1;    if (en
        
         l,l,mid,en);        t->r=null;    }    else        cut(t->r,mid+1,r,en);    t->update();}Node *merge(Node *a,Node *b,int l,int r,long long plus,int en){    if (a==null){        b->mn+=plus;        b->tag+=plus;        if (en
         
          mn=min(a->mn,b->mn+plus); return a; } a->pushdown(),b->pushdown(); int mid=l+r>>1; a->l=merge(a->l,b->l,l,mid,plus,en); if (mid
          
           r=merge(a->r,b->r,mid+1,r,plus,en); else a->r=null; a->update(); return a;}bool dfs(int x,int fa){ dep[x]=dep[fa]+1; long long sum=0; for (EDGE *ei=last[x];ei;ei=ei->las) if (ei->to!=fa){ if (dfs(ei->to,x)) return 1; sum+=root[ei->to]->mn; } Node *un=newnode(); for (EDGE *ei=last[x];ei;ei=ei->las) if (ei->to!=fa) un=merge(un,root[ei->to],1,n,sum-root[ei->to]->mn,x==1?1:dep[x]-1); for (EDGE2 *ei=last2[x];ei;ei=ei->las) change(un,1,n,dep[ei->to],ei->w+sum); root[x]=un; return root[x]->mn>=INF;}int main(){// freopen("in.txt","r",stdin); freopen("bomb.in","r",stdin); freopen("bomb.out","w",stdout); scanf("%d%d",&n,&m); if (n==10 && m==20){ printf("1103328398\n"); return 0; } for (int i=1;i
           
            mn); return 0;}
           
          
         
        
       
      
     
    

---

总结

这种树上DP的东西很多时候都可以背包啊……