因为南京出了题树的分治，特意去做了一下楼教主的分治入门题。
对于一棵树，先找到它的重心，然后计算一下经过根节点的合法路径有多少条，然后删掉改点，继续递归其他子树。复杂度n*logn*logn。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<map> #include<queue> #include<iostream> using namespace std; #define For(i,forN) for(int i=0;i<forN;i++) #define Rep(i,forN) for(int i=(forN);i>=0;i--) #define ForEdge(i,u) for(int i=head[u];i!=-1;i=edge[i].next) #define sf scanf #define pf printf #define mp make_pair #define _clr(x,y) memset(x,(y),sizeof(x)) /* 基于点的分治，先找到树的重心。 */ const int Maxn=11000,Maxe=Maxn*2; struct Edge{int to,next,cost; bool bvis;} edge[Maxe]; int head[Maxn],etot; int n,m,K; int dis[Maxn],pre[Maxn],child[Maxn][2],disFpre[Maxn],LongPath[Maxn],bleg[Maxn]; int que[Maxn],he,tail; bool vis[Maxn]; void add_edge(int u,int v,int cost) { edge[etot].cost=cost; edge[etot].to=v; edge[etot].next=head[u]; edge[etot].bvis=false; head[u]=etot++; } void init_edge() { etot=0; _clr(head,-1); } //避免使用dfs，而将以s为根的子树按拓扑序保存在队列que中,并记录pre[u],pre[root]=-1 void pushTreeInQue(int s) { que[he=0]=s,tail=1,vis[s]=true,pre[s]=-1; while(he<tail)//bfs一个拓扑序 { int u=que[he++]; ForEdge(i,u) { if(edge[i].bvis) continue; int v=edge[i].to; if(!vis[v]) { pre[v]=u; vis[v]=true; que[tail++]=v; } } } //将标记清空,但此时子树中的节点仍在队列中 For(i,tail) vis[que[i]]=false; } int findCenter(int s)//保证调用该函数时，s所在的子树标记已清空 { pushTreeInQue(s); dis[s]=0; for(int i=1;i<tail;i++) { int u=que[i]; dis[u]=0,child[u][0]=child[u][1]=-1; //child用来记录距离叶子节点最远的子节点,-1表示不存在 } for(int i=tail-1;i>0;i--)//相当于dfs的回溯 { int v=que[i],u=pre[v]; if(child[u][0]==-1 || dis[child[u][0]]<=dis[v])//最长的一条路径的起点为-1，或者长度较短 { child[u][1]=child[u][0]; child[u][0]=v; dis[u]=dis[v]+1; } else if(dis[child[u][1]]==-1 || dis[child[u][1]]<dis[v]) child[u][1]=v; } disFpre[s]=0; for(int i=0;i<tail;i++) { int u=que[i]; LongPath[u]=max(disFpre[u],dis[u]); ForEdge(j,u) { if(edge[j].bvis) continue; int v=edge[j].to; int tmp=(child[u][0]!=v && child[u][0]!=-1 ? dis[child[u][0]]+1 : 0); tmp=max(tmp,child[u][1]!=v && child[u][1]!=-1 ? dis[child[u][1]]+1 : 0); disFpre[v]=max(disFpre[u]+1,tmp); } } int ans=s; For(i,tail) if(LongPath[que[i]]<LongPath[ans]) ans=que[i]; return ans; } vector < int > tree[Maxn]; /* 必须保证solve在pushTreeInQue后，且没有修改过que、pre中的数据 计算每一个节点的dis，并求出节点属于哪颗子树 */ void pushDis(int cen) { queue < int > q; dis[cen]=0; q.push(cen); while(!q.empty()) { int u=q.front(); q.pop(); ForEdge(i,u) { int v=edge[i].to; if(pre[v]==u) { if(u==cen) bleg[v]=v; else bleg[v]=bleg[u]; dis[v]=dis[u]+edge[i].cost; q.push(v); } } } //将距离按子树分类，并排序 For(i,tail) tree[que[i]].clear(); tree[cen].push_back(0); for(int i=1;i<tail;i++) { tree[bleg[que[i]]].push_back(dis[que[i]]); tree[cen].push_back(dis[que[i]]); } sort(tree[cen].begin(),tree[cen].end()); for(int i=1;i<tail;i++) if(pre[que[i]]==cen) sort(tree[que[i]].begin(),tree[que[i]].end()); } int getCount(vector < int > &vec) { int l=vec.size(),r=-1,ans=0; For(i,l) if(vec[l-1]+vec[i]>K) break; else r=i; Rep(i,l-1) { while(r+1<l && vec[r+1]+vec[i]<=K) r++; ans+=min(i-1,r)+1; } return ans; } int solve(int cen)//找到重心后，根据题目意思实现solve函数 { pushTreeInQue(cen); pushDis(cen); int ans=getCount(tree[cen]); for(int i=1;i<tail;i++) if(pre[que[i]]==cen) ans-=getCount(tree[que[i]]); return ans; } int Divide() { queue < int > q; q.push(1); int ans=0; while(!q.empty()) { int u=q.front(); q.pop(); int cen=findCenter(u);//找到u所在的树的重心 ans+=solve(cen); ForEdge(i,cen)//所有跟cen相关的边都标记掉，并将其他子树加入队列 { if(edge[i].bvis) continue; edge[i].bvis=edge[i^1].bvis=true; q.push(edge[i].to); } } return ans; } int main() { while(~sf("%d%d",&n,&K) && (n||m)) { init_edge(); int u,v,cost; For(i,n-1) sf("%d%d%d",&u,&v,&cost),add_edge(u,v,cost),add_edge(v,u,cost); pf("%d ",Divide()); } } /* 8 10 1 2 1 2 3 3 3 4 7 4 5 4 5 8 2 3 6 6 6 7 3 */