每次找到去掉后剩下最大联通快最小的点，即重心计算贡献

#include 
     
      #include 
      
       #include 
       
        using namespace std;  int next[80001],des[80001],len[80001],nd[40001],cnt,bt[40001],dfstim,size[40001];  int msiz[40001],b[40001],maxsiz,grav,sta[40001],top,k,fin[40001];  long long ans;  void addedge(int x,int y,int le){      next[++cnt]=nd[x];des[cnt]=y;len[cnt]=le;nd[x]=cnt;  }    void dfs1(int po){      bt[po]=dfstim;size[po]=1;msiz[po]=0;      for (int p=nd[po];p!=-1;p=next[p])        if (b[des[p]]&&bt[des[p]]
        
         =0) sta[++top]=k-left;      if (left<0) return;      bt[po]=dfstim;            for (int p=nd[po];p!=-1;p=next[p])        if (b[des[p]]&&bt[des[p]]
         
          k) tmp--;            ans+=tmp;        }                for (int i=1;i<=top;i++) fin[++all]=sta[i];        sort(fin+1,fin+all+1);      }            for (int p=nd[grav];p!=-1;p=next[p])        if (b[des[p]])           work(des[p]);  }  int main(){      int n;      scanf("%d",&n);      for (int i=1;i<=n;i++) nd[i]=-1,b[i]=1;      for (int i=1;i
         
        
       
      
     

 --------------------------------------------------------

记录下树分治时的结构就可以支持一些修改操作

CODECHEF DEC17 CHEFFIB

#pragma GCC optimize(2)#include 
     
      #define LL long long using namespace std;     const LL mo=1e9+7;  LL transedA,transedB;  int bt[400001],dfstim,size[400001],msiz[400001],nd[400001],nxt[800001],des[800001],b[400001];  int maxsiz,grav,getrot[400001][21],getgrav[400001][21],getdis[400001][21],sta,root1[400001];  int ndcnt,mxdep[400001],root2[400001][21],cnt;  LL coef[4000001][2];    void init(){      coef[0][0]=1;coef[1][1]=1;      for (int i=2;i<=400000;i++)        coef[i][0]=(coef[i-1][0]+coef[i-2][0])%mo,        coef[i][1]=(coef[i-1][1]+coef[i-2][1])%mo;  }    struct treenode{      int lc,rc;      LL A,B,resA,resB;  }tr[10000001];      struct matrix{    LL a[601][601],tmp[601][601];    int n,m;          void mul(matrix &b){      for (int i=0;i
      
       >=1;        }    transedA=mata.a[0][0];transedB=mata.a[0][1];*/    transedA=(A*coef[stp][0]%mo+B*coef[stp][1]%mo)%mo;    transedB=(A*coef[stp+1][0]%mo+B*coef[stp+1][1]%mo)%mo;   }  void dfs1(int po){      bt[po]=dfstim;size[po]=1;msiz[po]=0;      for (int p=nd[po];p!=-1;p=nxt[p])        if (b[des[p]]&&bt[des[p]]
       
        >1;    trans(tr[tr[po].lc].resA,tr[tr[po].lc].resB,r-mid);    tr[po].resA=transedA+tr[tr[po].rc].resA;tr[po].resA%=mo;    tr[po].resB=transedB+tr[tr[po].rc].resB;tr[po].resB%=mo;  }  void edi(int po,int l,int r,int tar,LL A,LL B){      if (l==r){        tr[po].A+=A;tr[po].A%=mo;      tr[po].B+=B;tr[po].B%=mo;      tr[po].resA=tr[po].A;tr[po].resB=tr[po].B;      return;        }        int mid=(l+r)>>1;    if (tar<=mid){      if (!tr[po].lc) tr[po].lc=++ndcnt;      edi(tr[po].lc,l,mid,tar,A,B);    }else{      if (!tr[po].rc) tr[po].rc=++ndcnt;      edi(tr[po].rc,mid+1,r,tar,A,B);    }    update(po,l,r);  }  void ins(int gra,int po,int k,LL A,LL B,int dp){      if (gra==po){        edi(root1[po],1,mxdep[po],1,A,B);      if (k+2<=mxdep[po])        trans(A,B,k+1),        edi(root1[po],1,mxdep[po],k+2,-transedA,-transedB);          return;    }        int left=k-getdis[po][dp];    if (left>=0){      trans(A,B,getdis[po][dp]);      edi(root1[gra],1,mxdep[gra],1,transedA,transedB);      int rot2=root2[getrot[getgrav[po][dp+1]][dp]][dp];      trans(A,B,getdis[po][dp]);      edi(rot2,1,mxdep[gra],1,-transedA,-transedB);      if (left+2<=mxdep[gra]){          trans(A,B,k+1);         edi(root1[gra],1,mxdep[gra],left+2,-transedA,-transedB);          trans(A,B,k+1);        edi(rot2,1,mxdep[gra],left+2,transedA,transedB);        }            }    ins(getgrav[po][dp+1],po,k,A,B,dp+1);  }  LL getnum(int po,int l,int r,int tar){      LL ret=0;            int mid=(l+r)>>1;      if (tar==r) return(trans(tr[po].resA,tr[po].resB,tar-r),transedA);else      if (tar<=mid) return(getnum(tr[po].lc,l,mid,tar));else{        trans(tr[tr[po].lc].resA,tr[tr[po].lc].resB,tar-mid);      ret=transedA;      LL tmp=getnum(tr[po].rc,mid+1,r,tar);      ret+=tmp;      ret%=mo;      return(ret);        }  }  LL que(int gra,int po,int dp){      if (gra==po){        return(getnum(root1[gra],1,mxdep[gra],1));        }        LL ret=getnum(root1[gra],1,mxdep[gra],getdis[po][dp]+1);    int rot2=root2[getrot[getgrav[po][dp+1]][dp]][dp];    ret+=getnum(rot2,1,mxdep[gra],getdis[po][dp]+1);    ret%=mo;    ret+=que(getgrav[po][dp+1],po,dp+1);    ret%=mo;    return(ret);  }  int main(){      int T,n,q;      init();            scanf("%d",&T);      while (T--){        scanf("%d%d",&n,&q);cnt=0;      for (int i=1;i<=ndcnt;i++) tr[i].A=tr[i].B=tr[i].resA=tr[i].resB=tr[i].lc=tr[i].rc=0;          ndcnt=0;      for (int i=1;i<=n;i++) nd[i]=-1,b[i]=1;      for (int i=1;i
       
      
     

 __________________________________________________________

CODECHEF DEC15 WAYPA

树上最长回文路径。n<=100000

树分治时枚举回文串所在的较长的一侧。

void dfs3(int po,int rt,LL has,LL hasrev,LL powe){      ha[po]=has;harev[po]=hasrev;      mptot[has]++;      mp[rt][has]++;      bt[po]=dfstim;      for (int p=nd[po];p!=-1;p=nxt[p])        if (b[des[p]]&&bt[des[p]]
     
      =0;i--)        if (x&(1<
      
       mid) return;      if (dep[po]-1>=(mid+1)/2){        int t=getfa(po,mid-(dep[po]-1)),len=mid-(dep[po]-1);        if (ha[t]==harev[t])          if (mptot[ha[po]-ha[t]*pow233[len]]-mp[rt][ha[po]-ha[t]*pow233[len]])          flg=1;        }    for (int p=nd[po];p!=-1;p=nxt[p])      if (b[des[p]]&&bt[des[p]]