最大化access轻重链的切换次数

考虑一个点的贡献，即它交换重儿子的次数

发现这个次数只和它自己ai以及每个儿子的子树次数和有关。

 

一个关键的事实是：

我们可以自上而下进行贪心！

我们最大化fa的贡献，发现，对于操作序列，一个儿子子树的操作是一个子序列，不影响这个儿子子树的贡献！

（内部可以任意交换）

等价于：有m=|son|+1种颜色，每种颜色有若干个

排成一列，最大化相邻不相同颜色的次数

设颜色最多的是h，总和为t

则次数=min(t-1,2*(t-h))

证明的话：考虑先放那最多的h个然后插空，对于剩下的p=(t-h)个，如果p<=h-1，那么显然直接插空，贡献2*p个，如果p>h-1，那么一定可以不断来回插空，达到上界t-1

已经可以做不修改的了。

 

修改：

关键：1.只加w。2.考虑临界情况：2*h>=t+1时候，贡献2*(t-h)，否则贡献t-1。3.仅影响到根的链答案

如果一个点可以作为fa的最大值来源，则把这个链变成实链。

发现，修改一个点x时候，往上跳，实链还是实链，并且贡献还是不变的！

所以，只用考虑虚边的影响

发现，每跳一个虚边，所在子树的S*=2，所以最多log∑ai个

修改虚边：

减去原来的贡献，加上新来的贡献，分类讨论

用LCT的access实现跳跃实链

#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')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=4e5+5;int n,m;struct node{    int nxt,to;}e[2*N];int hd[N],cnt;ll ans;void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}struct tr{    int ch[2],fa;    ll v,s,si;    void out(){        cout<<" ch0 "<
          
           <<" ch1 "<
           
            <<" fa "<
            
             <
             
              mx){ mx=t[y].s;p=y; } } if(2*mx>=t[x].s+1){ if(p!=x) { rs=p;t[x].si-=t[p].s; } } ans+=min(t[x].s-1,2*(t[x].s-mx));}int main(){ int m; rd(n);rd(m); for(reg i=1;i<=n;++i){ rd(t[i].v); } int x,y; for(reg i=1;i
              
               2*t[y].s){ ans+=2*(S-t[rs].s); }else{ ans+=2*(S-t[y].s); t[x].si+=t[rs].s; t[x].si-=t[y].s; rs=y; } }else{ if(2*t[x].v
               
                
                 2*t[y].s){ ans+=2*(S-t[x].v); }else{ ans+=2*(S-t[y].s); t[x].si-=t[y].s; rs=y; } } }else{ if(rs){ if(2*t[rs].s
                 
                  
                   2*t[x].v){ ans+=2*(S-t[rs].s); }else{ ans+=2*(S-t[x].v); t[x].si+=t[rs].s; rs=0; } }else{ if(2*t[x].v
                   
                    
                     2*t[y].s){ ans+=2*(S-t[x].v); }else{ ans+=2*(S-t[y].s); t[x].si-=t[y].s; rs=y; } } } pushup(x); } printf("%lld\n",ans); } return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle* Date: 2019/4/13 19:58:12*/
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

1.考虑每个点的贡献！把题意进行转化

2.修改时候，考虑具体影响的部分是哪些。