每次找到去掉后剩下最大联通快最小的点，即重心计算贡献
#include <cstdio> #include <iostream> #include <algorithm> 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]]<dfstim){ dfs1(des[p]); msiz[po]=max(msiz[po],size[des[p]]); size[po]+=size[des[p]]; } } void dfs2(int po,int tot){ bt[po]=dfstim; if (max(msiz[po],tot-size[po])<maxsiz){ maxsiz=max(msiz[po],tot-size[po]); grav=po; } for (int p=nd[po];p!=-1;p=next[p]) if (b[des[p]]&&bt[des[p]]<dfstim) dfs2(des[p],tot); } int findgrav(int po){ dfstim++;dfs1(po); maxsiz=1e9; dfstim++;dfs2(po,size[po]); } void dfs3(int po,int left){ if (left>=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]]<dfstim) dfs3(des[p],left-len[p]); } void work(int po){ findgrav(po); b[grav]=0; int all=0; for (int p=nd[grav];p!=-1;p=next[p]) if (b[des[p]]){ dfstim++;top=0; dfs3(des[p],k-len[p]); ans+=top; sort(sta+1,sta+top+1); int tmp=all; for (int i=1;i<=top;i++){ while (sta[i]+fin[tmp]>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<n;i++){ int t1,t2,t3; scanf("%d%d%d",&t1,&t2,&t3); addedge(t1,t2,t3);addedge(t2,t1,t3); } scanf("%d",&k); work(1); printf("%lld ",ans); }
--------------------------------------------------------
记录下树分治时的结构就可以支持一些修改操作
CODECHEF DEC17 CHEFFIB
#pragma GCC optimize(2) #include <bits/stdc++.h> #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<n;i++) for (int j=0;j<b.m;j++) tmp[i][j]=0; for (int i=0;i<n;i++) for (int k=0;k<m;k++) if (a[i][k]) for (int j=0;j<b.m;j++) tmp[i][j]+=a[i][k]*b.a[k][j]%mo,tmp[i][j]%=mo; for (int i=0;i<n;i++) for (int j=0;j<b.m;j++) a[i][j]=tmp[i][j]; m=b.m; } }mata,matb; void addedge(int x,int y){ nxt[++cnt]=nd[x];des[cnt]=y;nd[x]=cnt; } void trans(LL A,LL B,int stp){ /*mata.a[0][0]=A;mata.a[0][1]=B;mata.n=1;mata.m=2; matb.a[1][0]=1;matb.a[0][1]=1;matb.a[1][1]=1;matb.a[0][0]=0;matb.n=matb.m=2; for (;stp;matb.mul(matb)){ if (stp&1) mata.mul(matb); stp>>=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]]<dfstim){ dfs1(des[p]); msiz[po]=max(msiz[po],size[des[p]]); size[po]+=size[des[p]]; } } void dfs2(int po,int tot){ bt[po]=dfstim; if (max(msiz[po],tot-size[po])<maxsiz){ maxsiz=max(msiz[po],tot-size[po]); grav=po; } for (int p=nd[po];p!=-1;p=nxt[p]) if (b[des[p]]&&bt[des[p]]<dfstim) dfs2(des[p],tot); } int findgrav(int po){ dfstim++;dfs1(po); maxsiz=1e9; dfstim++;dfs2(po,size[po]); } int dfs3(int po,int dp,int bel,int ori,int di){ getrot[po][dp]=bel; getgrav[po][dp]=ori; getdis[po][dp]=di; bt[po]=dfstim; int ret=1; for (int p=nd[po];p!=-1;p=nxt[p]) if (b[des[p]]&&bt[des[p]]<dfstim) ret=max(ret,dfs3(des[p],dp,bel,ori,di+1)+1); return(ret); } void work(int po,int dp){ findgrav(po); getgrav[grav][dp]=grav; if (dp==1) sta=grav; b[grav]=0; root1[grav]=++ndcnt; mxdep[grav]=1; for (int p=nd[grav];p!=-1;p=nxt[p]) if (b[des[p]]){ root2[des[p]][dp]=++ndcnt; dfstim++; mxdep[grav]=max(mxdep[grav],dfs3(des[p],dp,des[p],grav,1)+1); } for (int p=nd[grav];p!=-1;p=nxt[p]) if (b[des[p]]) work(des[p],dp+1); } void update(int po,int l,int r){ int mid=(l+r)>>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<n;i++){ int t1,t2; scanf("%d%d",&t1,&t2); addedge(t1,t2);addedge(t2,t1); } work(1,1); while (q--){ int opt,t1,t2; LL t3,t4; scanf("%d",&opt); if (opt==1){ scanf("%d%d%lld%lld",&t1,&t2,&t3,&t4); ins(sta,t1,t2,t3,t4,1); }else{ scanf("%d",&t1); printf("%lld ",(que(sta,t1,1)%mo+mo)%mo); } } } }
__________________________________________________________
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]]<dfstim){ fa[des[p]][0]=po;dep[des[p]]=dep[po]+1; for (int j=1;j<=20;j++) fa[des[p]][j]=fa[fa[des[p]][j-1]][j-1]; dfs3(des[p],rt,has*bas+len[p]+1,hasrev+powe*(len[p]+1)*bas,powe*bas); } } int getfa(int po,int x){ for (int i=20;i>=0;i--) if (x&(1<<i)) po=fa[po][i]; return(po); } void dfs4(int po,int rt){ bt[po]=dfstim; if (dep[po]-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]]<dfstim) dfs4(des[p],rt); }