数据结构最后一个基础算法了、、总算开始学了

先阅读了《分治算法在树的路径问题中的应用》，好不容易找到不要钱的

然后按照上面讲的一步一步写下来

树的重心模板（POJ1655）

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 111111
using namespace std;
int T,n,i,x,y,root,ans,tot,first[N],mav[N],size[N],next[N<<1],last[N<<1];
bool vis[N];
void insert(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
void dfs(int x){
	size[x]=1;mav[x]=0;
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(!vis[y]){
			vis[y]=1;
			dfs(y);
			size[x]+=size[y];
			mav[x]=max(mav[x],size[y]);
		}
	}
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		memset(first,0,sizeof(first));
		memset(vis,0,sizeof(vis));
		tot=0;
		for(i=1;i<n;i++)scanf("%d%d",&x,&y),insert(x,y),insert(y,x);
		vis[1]=1;dfs(1);
		ans=99999999;root=0;
		for(i=1;i<=n;i++){
			mav[i]=max(mav[i],n-size[i]);
			if(mav[i]<ans)ans=mav[i],root=i;
		}
		printf("%d %d\n",root,ans);
	}
}

【例1】POJ1741（给一棵边带权树，问两点之间的距离小于等于K的点对有多少个）

一路分治下来，每次选重心点算每个点到重心点的距离，统计一下<=K的路径条数，再减去从同一子节点弄上来的两条路径，复杂度O(n log^2n)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 11111
using namespace std;
int n,k,i,x,y,z,ans,root,tot,top,val,next[N<<1],last[N<<1],value[N<<1],first[N],size[N],mav[N],num[N];
bool vis[N];
void insert(int x,int y,int z){last[++tot]=y;next[tot]=first[x];value[tot]=z;first[x]=tot;}
void dfssize(int x,int fa){//第一遍遍历
	size[x]=1;mav[x]=0;
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=fa&&!vis[y]){
			dfssize(y,x);
			size[x]+=size[y];
			mav[x]=max(mav[x],size[y]);
		}
	}
}
void dfsroot(int zs,int x,int fa){//求重心
	if(size[zs]-size[x]>mav[x])mav[x]=size[zs]-size[x];
	if(mav[x]<val)val=mav[x],root=x;
	for(int i=first[x];i;i=next[i])
		if(last[i]!=fa&&!vis[last[i]])dfsroot(zs,last[i],x);
}
void dfsdis(int x,int fa,int dis){//统计距离
	num[++top]=dis;
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=fa&&!vis[y])dfsdis(y,x,dis+value[i]);
	}
}
int calc(int x,int co){
	int now=0,i,j;top=0;
	dfsdis(x,0,co);
	sort(num+1,num+top+1);//统计出所有路径的条数并排序
	for(i=1,j=top;i<j;i++){//处理出<=k的路径条数
		while(num[i]+num[j]>k&&i<j)j--;
		now+=(j-i);
	}
	return now;
}
void dfs(int x){
	val=99999999;
	dfssize(x,0);
	dfsroot(x,x,0);//求出树的重心
	ans+=calc(root,0);//统计以重心为根所有路径符合条件的个数
	vis[root]=1;
	for(int i=first[root];i;i=next[i]){
		int y=last[i];
		if(!vis[y]){
			ans-=calc(y,value[i]);//减去从同一子节点上来的路径
			dfs(y);
		}
	}
}
int main(){
	while(1){
		scanf("%d%d",&n,&k);
		if(!n&&!k)return 0;
		memset(first,0,sizeof(first));memset(vis,0,sizeof(vis));tot=0;ans=0;
		for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),insert(x,y,z),insert(y,x,z);
		dfs(1);
		printf("%d\n",ans);
	}
}

BZOJ2152聪聪可可：点分治，同上

#include<cstdio>
#include<iostream>
#define N 22222
#define inf 99999999
using namespace std;
int n,i,x,y,z,tot,val,root,ans,fm,gy,num[3],last[N<<1],value[N<<1],next[N<<1],first[N],mav[N],size[N];
bool vis[N];
int gcd(int x,int y){if(!x)return y;return gcd(y%x,x);}
void insert(int x,int y,int z){last[++tot]=y;value[tot]=z;next[tot]=first[x];first[x]=tot;}
void dfssize(int x,int fa){
	size[x]=1;mav[x]=0;
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=fa&&!vis[y])dfssize(y,x),size[x]+=size[y],mav[x]=max(mav[x],size[y]);
	}
}
void dfsroot(int g,int x,int fa){
	if(size[g]-size[x]>mav[x])mav[x]=size[g]-size[x];
	if(mav[x]<val)val=mav[x],root=x;
	for(int i=first[x];i;i=next[i])
		if(last[i]!=fa&&!vis[last[i]])dfsroot(g,last[i],x);
}
void dfsdis(int x,int fa,int dis){
	num[dis]++;
	for(int i=first[x];i;i=next[i]){
		int y=last[i];
		if(y!=fa&&!vis[y])dfsdis(y,x,(dis+value[i])%3);
	}
}
int calc(int x,int co){
	num[0]=num[1]=num[2]=0;
	dfsdis(x,0,co);
	return num[0]*num[0]+num[1]*num[2]*2;
}
void dfs(int x){
	val=inf;
	dfssize(x,0);
	dfsroot(x,x,0);
	ans+=calc(root,0);
	vis[root]=1;
	for(int i=first[root];i;i=next[i]){
		int y=last[i];
		if(!vis[y])ans-=calc(y,value[i]),dfs(y);
	}
}
int main(){
	scanf("%d",&n);
	for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),z%=3,insert(x,y,z),insert(y,x,z);
	dfs(1);
	fm=n*n;gy=gcd(ans,fm);
	ans/=gy;fm/=gy;
	printf("%d/%d",ans,fm);
}♀大

BZOJ1758 首先二分答案转变为判断可行性问题，对于一个分治结构，得到其一个子树下所有深度的最好值，和当前的最好值进行正反两遍单调队列，分别表示i-R+L~i的值和i~i+R-L的值，这样就可以保证时间复杂度为O(nlgnlg1e9)

#include<bits/stdc++.h>
#define N 100100
#define inf -1e17
using namespace std;
int n,i,L,R,x,y,h,t,rt,tot,fir[N],Fir[N],mv[N],sz[N],q[N],la[N<<2],ne[N<<2];
double l,r,mid,ans,z,va[N<<2],a[N],b[N];bool vis[N],ff;
void ins(int x,int y,double z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void Ins(int x,int y){la[++tot]=y;va[tot]=z;ne[tot]=Fir[x];Fir[x]=tot;}
void dsz(int x,int fa){
	sz[x]=1;mv[x]=0;
	for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)dsz(y,x),sz[x]+=sz[y],mv[x]=max(mv[x],sz[y]);
}
void drt(int zs,int x,int fa,int &rt){
	mv[x]=max(mv[x],sz[zs]-sz[x]);if(mv[x]<mv[rt]||!rt)rt=x;
	for(int i=fir[x];i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
int fz(int x){
	int i,p,rt=0;dsz(x,0);drt(x,x,0,rt);vis[rt]=1;
	for(i=fir[rt];i;i=ne[i])if(!vis[la[i]])Ins(rt,fz(la[i]));
	return rt;
}
void tour(int x,int fa,int dp,double w,double z,int&de){
	b[dp]=max(b[dp],w);de=max(de,dp);
	for(int i=fir[x];i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)tour(la[i],x,dp+1,w+va[i]-z,z,de);
}
void get(int x,double z){
	if(ans>0)return;int i,j,h,t,de,st=0;vis[x]=1;
	for(i=fir[x];i;i=ne[i])if(!vis[la[i]]){
		de=t=0;h=1;tour(la[i],x,1,va[i]-z,z,de);st=max(st,de);
		for(j=0;j<=de;j++){
			for(;h<=t&&q[h]<j-R+L;h++);
			for(;h<=t&&b[j]>=b[q[t]];t--);
			q[++t]=j;ans=max(ans,a[R-j]+b[q[h]]);
			if(ans>0)return;
		}
		for(t=0,h=1,j=de;j>=0;j--){
			for(;h<=t&&q[h]>j+R-L;h++);
			for(;h<=t&&b[j]>=b[q[t]];t--);
			q[++t]=j;ans=max(ans,a[L-j]+b[q[h]]);
			if(ans>0)return;
		}
		for(j=1;j<=de;j++)a[j]=max(a[j],b[j]),b[j]=inf;
	}
	for(i=1;i<=st;i++)a[i]=inf;
	for(i=Fir[x];i;i=ne[i])get(la[i],z);
}
bool ok(double z){memset(vis,0,sizeof(vis));ans=inf;for(i=1;i<=n;i++)a[i]=b[i]=inf;get(rt,z);return ans>0;}
int main(){
	for(scanf("%d%d%d",&n,&L,&R),i=1;i<n;i++)scanf("%d%d%lf",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	for(rt=fz(1),l=0,r=1000000;r-l>1e-5;)if(ok(mid=(l+r)/2))l=mid;else r=mid;
	printf("%.3lf",l);
}

今天第N次看动态树分治，总算看懂了。。

大概就是像点分治一样先维护出一颗重心树来，然后每个点用数据结构维护

BZOJ1095

对于每个点，用A[]记录该点子树中所有点到其距离，用B[]记录各个儿子A[]的最大值，用C记录全局B的最大值和次大值，每次的答案就是C的最大值

对于修改操作，只会修改一条链，那么在这条链上修改所有的A[]、B[]并更新C[]就可以了

#include<bits/stdc++.h>
#define N 100100
using namespace std;char s[9];
int n,m,i,x,y,tot,cnt,fir[N],d[N],sz[N],mv[N],ne[N<<1],la[N<<1],F[N][17],fa[N];bool vis[N],co[N];
multiset<int>A[N],B[N],C;multiset<int>::iterator it;
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void Ins(multiset<int>a){if(a.size()>=2)it=--a.end(),C.insert(*it+(*--it));}
void Del(multiset<int>a){if(a.size()>=2)it=--a.end(),C.erase(C.find(*it+(*--it)));}
void dfs(int x){
	for(int i=1;i<=16;i++)F[x][i]=F[F[x][i-1]][i-1];
	for(int i=fir[x];i;i=ne[i])if(F[x][0]!=la[i])d[la[i]]=d[x]+1,F[la[i]][0]=x,dfs(la[i]);
}
void dsz(int x,int fa){
	sz[x]=1;mv[x]=0;
	for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa){
		dsz(y,x);sz[x]+=sz[y];mv[x]=max(mv[x],sz[y]);
	}
}
void drt(int zs,int x,int fa,int &rt){
	mv[x]=max(mv[x],sz[zs]-sz[x]);
	if(mv[x]<mv[rt]||!rt)rt=x;
	for(int i=fir[x];i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
void get(int x,int fa,int de,multiset<int>&s){
	s.insert(de);
	for(int i=fir[x];i;i=ne[i])if(!vis[la[i]]&&la[i]!=fa)get(la[i],x,de+1,s);
}
int fz(int x){
	int i,p,rt=0;dsz(x,0);drt(x,x,0,rt);vis[rt]=1;
	B[rt].insert(0);
	for(i=fir[rt];i;i=ne[i])if(!vis[la[i]]){
		multiset<int>s;get(la[i],0,1,s);
		p=fz(la[i]);fa[p]=rt;A[p]=s;
		B[rt].insert(*--A[p].end());
	}
	Ins(B[rt]);return rt;
}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);int t=d[x]-d[y],i;
    for(i=0;i<=16;i++)if(t&(1<<i))x=F[x][i];
    for(i=16;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
    return x==y?x:F[x][0];
}
int dis(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
void cha(int x,bool f){
	Del(B[x]);if(f)B[x].erase(B[x].find(0));else B[x].insert(0);Ins(B[x]);
	for(int i=x,y;fa[i];i=fa[i]){
		Del(B[y=fa[i]]);
		if(A[i].size())B[y].erase(B[y].find(*--A[i].end()));
		if(f)A[i].erase(A[i].find(dis(y,x)));else A[i].insert(dis(y,x));
		if(A[i].size())B[y].insert(*--A[i].end());
		Ins(B[y]);
	}
}
int main(){
	for(scanf("%d",&n),cnt=n,i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(dfs(1),fz(1),scanf("%d",&m);m--;){
		scanf("%s",s);
		if(s[0]=='G')if(cnt<=1)printf("%d\n",cnt-1);else printf("%d\n",*--C.end());
		else scanf("%d",&x),co[x]^=1,cha(x,co[x]);
	}
}

BZOJ3924 就是省选题。先弄出分治树，然后更新答案在分治出来的树上更新，维护每个分治树内的答案和对外面的影响，预处理LCA，O(1)询问，总时间复杂度O(knlg^2n)

#include<bits/stdc++.h>
#define N 100100
using namespace std;typedef long long LL;LL F[N<<1][18],d[N],s1[N],s2[N],w1[N],w2[N];bool vis[N];
int n,m,i,j,x,y,z,mt,rt,tot,gl[N<<1],fir[N],Fir[N],mv[N],sz[N],fa[N],la[N<<2],ne[N<<2],va[N<<2],pos[N];
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;}
void Ins(int x,int y,int z){la[++tot]=y;ne[tot]=Fir[x];va[tot]=z;Fir[x]=tot;fa[z]=x;}
void dfs(int x,int fa){
	F[pos[x]=++mt][0]=d[x];
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)d[la[i]]=d[x]+va[i],dfs(la[i],x),F[++mt][0]=d[x];
}
void dsz(int x,int fa){
	sz[x]=1;mv[x]=0;
	for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)dsz(y,x),sz[x]+=sz[y],mv[x]=max(mv[x],sz[y]);
}
void drt(int zs,int x,int fa,int&rt){
	mv[x]=max(mv[x],sz[zs]-sz[x]);if(mv[x]<mv[rt]||!rt)rt=x;
	for(int i=fir[x];i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
int fz(int x){
	int i,p,rt=0;dsz(x,0);drt(x,x,0,rt);vis[rt]=1;
	for(i=fir[rt];i;i=ne[i])if(!vis[la[i]])Ins(rt,la[i],fz(la[i]));
	return rt;
}
int dis(int x,int y){
	int w=d[x]+d[y],t;x=pos[x];y=pos[y];
	if(x>y)swap(x,y);t=gl[y-x+1];
	return w-2*min(F[x][t],F[y-(1<<t)+1][t]);
}
LL add(int x,int z){
	s1[x]+=z;
	for(int i=x,y;fa[i];i=fa[i])y=dis(fa[i],x),w1[fa[i]]+=(LL)y*z,w2[i]+=(LL)y*z,s1[fa[i]]+=z,s2[i]+=z;
}
LL cal(int x){
	LL ans=w1[x];
	for(int i=x,y;fa[i];i=fa[i])y=dis(fa[i],x),ans+=(w1[fa[i]]-w2[i]+(s1[fa[i]]-s2[i])*y);
	return ans;
}
LL qu(int x){
	LL ans=cal(x),w;
	for(int i=Fir[x];i;i=ne[i]){
		w=cal(la[i]);
		if(w<ans)return qu(va[i]);
	}
	return ans;
}
int main(){
	for(scanf("%d%d",&n,&m),i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	for(dfs(1,0),i=2;i<=mt;i++)gl[i]=gl[i>>1]+1;
	for(j=1;j<=gl[mt];j++)for(i=1;i+(1<<j)-1<=mt;i++)F[i][j]=min(F[i][j-1],F[i+(1<<j-1)][j-1]);
	for(rt=fz(1);m--;printf("%lld\n",qu(rt)))scanf("%d%d",&x,&z),add(x,z);
}

BZOJ3730 辣鸡卡常题

#include<bits/stdc++.h>
#define N 101000
using namespace std;typedef long long LL;bool v[N];LL ans,sm[N*60];
int n,Q,i,j,o,x,y,z,rt,id,di,tot,a[N],fir[N],ne[N*2],la[N*2],F[N],G[N*2][18],f[N],sz[N],d[N],pos[N],gl[N*2],A[N],B[N],L[N*60],R[N*60];
char ch;inline void Z(int &x){
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
inline void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
inline void dfs(int x,int fa){
	G[pos[x]=++id][0]=d[x];
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)d[la[i]]=d[x]+1,dfs(la[i],x),G[++id][0]=d[x];
}
inline int dis(int x,int y){
	int w=d[x]+d[y],t;x=pos[x];y=pos[y];
	if(x>y)swap(x,y);t=gl[y-x+1];
	return w-2*min(G[x][t],G[y-(1<<t)+1][t]);
}
inline void dsz(int x,int fa){
	sz[x]=1;f[x]=0;
	for(int i=fir[x],y;i;i=ne[i])if(!v[y=la[i]]&&y!=fa)dsz(y,x),sz[x]+=sz[y],f[x]=max(f[x],sz[y]);
}
inline void drt(int zs,int x,int fa,int&rt){
	f[x]=max(f[x],sz[zs]-sz[x]);if(f[x]<f[rt]||!rt)rt=x;
	for(int i=fir[x];i;i=ne[i])if(!v[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
inline void ins(int&k,int l,int r,int x,int z){
	if(!k)k=++di;sm[k]+=z;if(l==r)return;int M=l+r>>1;
	if(x<=M)ins(L[k],l,M,x,z);else ins(R[k],M+1,r,x,z);
}
inline LL qu(int k,int l,int r,int x){
	if(!k||x<l)return 0;if(r<=x)return sm[k];int M=l+r>>1;
	return qu(L[k],l,M,x)+qu(R[k],M+1,r,x);
}
inline void cal(int x,int fa,int E,int&rt){
	ins(rt,0,n,dis(x,E),a[x]);
	for(int i=fir[x],y;i;i=ne[i])if(!v[y=la[i]]&&y!=fa)cal(y,x,E,rt);
}
inline int fz(int x,int fa){
	int i,R=0,y,p;dsz(x,0);drt(x,x,0,R);cal(R,0,R,A[R]);v[R]=1;F[R]=fa;
	for(i=fir[R];i;i=ne[i])if(!v[y=la[i]])cal(y,R,R,p=0),B[fz(y,R)]=p;
	return R;
}
inline void cha(int x,int z){
	ins(A[x],0,n,0,z);
	for(int i=x,o;F[i];i=F[i])o=dis(x,F[i]),ins(A[F[i]],0,n,o,z),ins(B[i],0,n,o,z);
}
inline LL qu(int x,int k){
	LL V=qu(A[x],0,n,k);int i=x,o;
	for(;F[i];i=F[i])o=dis(x,F[i]),V+=qu(A[F[i]],0,n,k-o)-qu(B[i],0,n,k-o);
	return V;
}
int main(){
	for(Z(n),Z(Q),i=1;i<=n;i++)Z(a[i]);
	for(i=1;i<n;i++)Z(x),Z(y),ins(x,y),ins(y,x);
	for(dfs(1,0),i=2;i<=id;i++)gl[i]=gl[i>>1]+1;
	for(j=1;j<=gl[id];j++)for(i=1;i+(1<<j)-1<=id;i++)G[i][j]=min(G[i][j-1],G[i+(1<<j-1)][j-1]);
	for(rt=fz(1,0);Q--;)
		if(Z(o),Z(x),Z(y),x^=ans,y^=ans,o)z=y-a[x],a[x]=y,cha(x,z);else ans=qu(x,y),printf("%lld\n",ans);
}

BZOJ2051&4317 先一遍树分治，得到一个距离序列，用vector记录并排序，然后对每个点统计答案时二分+判定，判定时候再二分，总复杂度O(nlg^3n)

#include<bits/stdc++.h>
#define N 15050
using namespace std;vector<int>v1[N],v2[N];bool vis[N];
int n,k,i,x,y,z,D,l,r,mid,rt,tot,sz[N],mv[N],fa[N],d[N],h[N],F[N][14],fir[N],ne[N<<1],la[N<<1],va[N<<1];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
	for(int i=1;i<=13;i++)F[x][i]=F[F[x][i-1]][i-1];
	for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa)F[y=la[i]][0]=x,h[y]=h[x]+1,d[y]=d[x]+va[i],dfs(y,x);
}
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);int t=h[x]-h[y],i;
    for(i=0;i<=13;i++)if(t>>i&1)x=F[x][i];
    for(i=13;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
    return x==y?x:F[x][0];
}
int dis(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
void dsz(int x,int fa){
    sz[x]=1;mv[x]=0;
    for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)dsz(y,x),sz[x]+=sz[y],mv[x]=max(mv[x],sz[y]);
}
void drt(int zs,int x,int fa,int&rt){
    mv[x]=max(mv[x],sz[zs]-sz[x]);if(mv[x]<mv[rt]||!rt)rt=x;
    for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
void get(int x,int fa,int z,vector<int>&w){
	w.push_back(z);
	for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)get(y,x,z+va[i],w);
}
int fz(int x){
    int i,p,rt=0;dsz(x,0);drt(x,x,0,rt);vis[rt]=1;get(rt,0,0,v1[rt]);
    for(i=fir[rt];i;i=ne[i])if(!vis[la[i]]){
    	vector<int>o;get(la[i],rt,va[i],o);
		fa[p=fz(la[i])]=rt;v2[p]=o;
	}
	return rt;
}
int ask(int w,int z){
	int l=1,r=v1[w].size(),mid,ans=0;
	for(;l<=r;)if(mid=l+r>>1,z>=v1[w][mid-1])ans=mid,l=mid+1;else r=mid-1;
	return ans;
}
int ask2(int w,int z){
	int l=1,r=v2[w].size(),mid,ans=0;
	for(;l<=r;)if(mid=l+r>>1,z>=v2[w][mid-1])ans=mid,l=mid+1;else r=mid-1;
	return ans;
}
int cal(int x,int z){
	int now=ask(x,z),i=x;
	for(;fa[i];i=fa[i])D=dis(x,fa[i]),now+=ask(fa[i],z-D)-ask2(i,z-D);
	return now;
}
int qu(int x){
	for(l=0,r=10*n;l<r;)if(cal(x,mid=l+r>>1)<=k)l=mid+1;else r=mid;
	return l;
}
int main(){
	for(scanf("%d%d",&n,&k),i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
	for(dfs(1,0),rt=fz(1),i=1;i<=n;i++)sort(v1[i].begin(),v1[i].end()),sort(v2[i].begin(),v2[i].end());
	for(i=1;i<=n;i++)printf("%d\n",qu(i));
}

BZOJ2566 动态树分治+map套set

#include<bits/stdc++.h>
#define N 12121
using namespace std;bool vis[N];multiset<int>A[N],B[N],C[N];
struct W{
    multiset<int>A,B;
    int G(){
        if(A.size()<2)return 1e9;int x=*A.begin();
        multiset<int>::iterator it=A.begin();return x+(*++it);
    }
};map<int,W>mp[N];map<int,W>::iterator it;multiset<int>U;
int n,m,i,j,x,y,z,rt,tot,id,c[N],d[N],h[N],fir[N],ne[N*2],la[N*2],va[N*2],F[N][14],mv[N],sz[N],fa[N],q[N];
void D(multiset<int>&S,int x){S.erase(S.find(x));}
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa){
    for(int i=1;i<14;i++)F[x][i]=F[F[x][i-1]][i-1];
    for(int i=fir[x],y;i;i=ne[i])if(la[i]!=fa)F[y=la[i]][0]=x,h[y]=h[x]+1,d[y]=d[x]+va[i],dfs(y,x);
}
int lca(int x,int y){
    if(h[x]<h[y])swap(x,y);int t=h[x]-h[y],i;
    for(i=0;i<14;i++)if(t>>i&1)x=F[x][i];
    for(i=13;i>=0;i--)if(F[x][i]!=F[y][i])x=F[x][i],y=F[y][i];
    return x==y?x:F[x][0];
}
int dis(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
void dsz(int x,int fa){
    sz[x]=1;mv[x]=0;
    for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)dsz(y,x),sz[x]+=sz[y],mv[x]=max(mv[x],sz[y]);
}
void drt(int zs,int x,int fa,int &rt){
    mv[x]=max(mv[x],sz[zs]-sz[x]);if(mv[x]<mv[rt]||!rt)rt=x;
    for(int i=fir[x];i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
void get(int x,int fa,int z,int rt){
    if(mp[rt].count(c[x]))mp[rt][c[x]].A.insert(z);else {W o;o.A.insert(z);mp[rt][c[x]]=o;}
    for(int i=fir[x],y;i;i=ne[i])if(!vis[y=la[i]]&&y!=fa)get(y,x,z+va[i],rt);
}
int fz(int x){
    int i,p,rt=0;dsz(x,0);drt(x,x,0,rt);vis[rt]=1;
    for(get(rt,0,0,rt),it=mp[rt].begin();it!=mp[rt].end();it++)it->second.B.insert(it->second.G());
    for(i=fir[rt];i;i=ne[i])if(!vis[la[i]])for(p=fz(la[i]),fa[p]=rt,it=mp[p].begin();it!=mp[p].end();it++)mp[rt][it->first].B.insert(*(it->second.B.begin()));
    return rt;
}
void add(int x,int z,int lx){
    if(mp[rt].count(z))D(U,*mp[rt][z].B.begin());
    int t=0,u=x,i;
    for(;u;u=fa[u])q[++t]=u;
    for(i=t;i>1;i--)if(mp[q[i-1]].count(z))D(mp[q[i]][z].B,*mp[q[i-1]][z].B.begin());
    if(lx)for(i=1;i<=t;i++)if(mp[q[i]].count(z))D(mp[q[i]][z].B,mp[q[i]][z].G());
    for(i=x;i;i=u){
        if(lx)mp[i][z].A.insert(dis(x,i));else D(mp[i][z].B,mp[i][z].G()),D(mp[i][z].A,dis(x,i));
        mp[i][z].B.insert(mp[i][z].G());if(u=fa[i])mp[u][z].B.insert(*mp[i][z].B.begin());
    }
    U.insert(*mp[rt][z].B.begin());
}
int main(){
    for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&c[i]);
    for(i=1;i<n;i++)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
    for(dfs(1,0),rt=fz(1),it=mp[rt].begin();it!=mp[rt].end();it++)U.insert(*(it->second.B.begin()));
    for(printf("%d\n",*(U.begin())),scanf("%d",&m);m--;printf("%d\n",*(U.begin())))scanf("%d%d",&x,&y),add(x,c[x],0),add(x,y,1),c[x]=y;
}

• 相关文章推荐
• 全局相关文章