另类复杂度分析题

对于给定的d

f[x][0/1]x为根的子树，到父亲的边连不连，整个子树的花费最小值

转移时候，设要删掉k的出边，都先变成∑f[son][1]，再把f[son][0]+vf[son]-f[son][1]插入堆中，取最小的k个

当f[son][0]+vf[son]-f[son][1]<0一定选择，先选上，令k--

 

所有的d

对于du[x]<=d的x，其度数最后是多少都满足，所以可以不用管了。删除这个点和出边

对剩下的点的连通块进行上述dp

 

很麻烦的事情：

1.du[x]<=d的x删除了，但是其实还要考虑是否会删除

所以把x的所有出边(y,val)的y的堆里面加入val，设这些边为特殊边

2.处理的时候，把会访问儿子的f[son][0]+vf[son]-f[son][1]也加入堆中，

设需要删除k条边

把堆的限制卡成k。然后堆内元素的和就是前k小的值

但是需要还原，所以这个时候删除的东西再用vector存，然后还原，把访问的儿子的f[son][0]+vf[son]-f[son][1]再删除

所以，堆需要懒惰删除+查询总和

堆是大根堆

（或者手写平衡树查前k小？）

3.如果用堆

那么对于特殊边，也要先卡成k，这些扔掉的特殊边就不用了（因为k单调）

这样，每次求dp时候暴力卡成k复杂度就是对的。

否则菊花图就完了。

 

每个点会被访问du[x]次，总复杂度O(nlogn)

#include
     
      #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
      
       using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
   if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
   if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=250000+5;int n;int du[N],rk[N];bool cmp1(int x,int y){ return du[x]
           
            du[y];}struct node{ int to;ll val; node(){} node(int x,ll v){ to=x;val=v; } bool friend operator <(node a,node b){ return du[a.to]>du[b.to]; }};vector
            
             to[N];int sta[N],top;bool vis[N];ll f[N][2];struct Heap{ priority_queue
             
              q,d; int sz; ll sum; void dele(ll v){ d.push(v);--sz;sum-=v; } void ins(ll v){ q.push(v);++sz;sum+=v; } ll top(){ while(q.size()&&d.size()&&q.top()==d.top()) q.pop(),d.pop(); if(q.size()) return q.top(); return -2333; } void pop(){ while(q.size()&&d.size()&&q.top()==d.top()) q.pop(),d.pop(); if(q.size()){ sum-=q.top();--sz; q.pop(); } }}hp[N];int lim;void sol(int x){// cout<<" sol "<
              
               <
               
                m) hp[x].pop(); vis[x]=1; ll tot=0; vector
                
                 a,b; for(solid y:to[x]){ if(vis[y.to]) continue; sol(y.to); if(f[y.to][0]+y.val-f[y.to][1]<0) --m,tot+=f[y.to][0]+y.val; else{ tot+=f[y.to][1]; hp[x].ins(f[y.to][0]+y.val-f[y.to][1]); b.push_back(f[y.to][0]+y.val-f[y.to][1]); } }// cout<<" m1 "<
                 
                  <<" "<
                  
                   <<" sz "<
                   
                    <
                    
                     m) { a.push_back(hp[x].top()); hp[x].pop(); }// cout<<" end "<
                     
                      <
                      
                       m){ a.push_back(hp[x].top()); hp[x].pop(); } f[x][0]=tot+hp[x].sum; for(solid v:a) hp[x].ins(v); for(solid v:b) hp[x].dele(v);// cout<<" tot "<
                       
                        <<" m2 "<
                        
                         <