具体算法可以看 2009 年的漆子超的论文
以合法点对为例：
进行分治，由于每次找的是重心，深度做多是log(n)。
大体来说就是
1：先找到该该数的重心，只需要把数遍历一遍就好了。复杂度：o(n)
2：计算各个节点到重心的距离。复杂度：o(n)
3：对重心距离进行排序，然后计算d[i]+d[j]<=k的合法点对。复杂度：排序o(nlog(n))，计算o(n)
所以总的复杂度为o(n*log(n)*log(n))
#include#include #define INF 1<<30using namespace std;struct Edge{ int next,to; int w;}edge[MAXN<<1]; ///边的信息int son[MAXN]; ///该子树共有的节点数int size; ///分治以后一颗新树所包含的所有节点数int list[MAXN]; ///保存遍历的这颗树的所有节点信息int ss[MAXN]; ///保存所有节点的子树节点数的最大值int d[MAXN]; ///保存节点到根的距离bool vis[MAXN]; ///该节点有无删除int k; ///d[i]+d[j]<=kint cnt; ///边的个数int num; ///使节点值变成一个数列int ans; ///保存最终答案int head[MAXN]; ///邻接表void add_edge(int u,int v,int w){ edge[cnt].to = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++;}void init(){ cnt = ans =0; memset(head,-1,sizeof(head)); memset(vis,false,sizeof(vis));}///第一步，要找到重心作为根节点void dfs_size(int u,int fa){ list[size++] = u; son[u] = 1; int tem = -1; for(int i = head[u];i != -1;i = edge[i].next){ int v = edge[i].to; if(!vis[i] && v != fa){ dfs_size(v,u); son[u] += son[v]; tem = max(tem,son[v]); } } ss[u] = tem;}int getroot(int u){ size = 0; dfs_0(u,-1); int m_sum = INF,rt; for(int i = 0;i < size;i++){ int v = list[i]; ss[v] = max(ss[v],size-son[v]); if(ss[v] < m_sum){ m_sum = ss[v]; rt = v; } } return rt;}///计算所有节点到根的距离void dfs_dist(int u,int dis,int fa){ d[num++] = dis; for(int i = head[u];i != -1;i = edge[i].next){ int v = edge[i].to; if(!vis[v] && v !=fa) dfs_dist(v,dis+edge[i].w,u); }}///计算合法点对int calc(int u,int dis){ num = 0; dfs_dist(u,dis,-1); sort(d,d+num); int ret = 0; int i = 0,j = num-1; while(i < j){ while(d[i]+d[j] > k && i < j) j--; ret += (j-i); i++; } return ret;}///进行分治和计算最终答案void dfs(int u){ int rt = getroot(u); ans += calc(rt,0); vis[rt] = true; for(int i = head[rt];i != -1;i = edge[i].next){ int v = edge[i].to; if(!vis[v]){ ans -= calc(v,edge[i].w); dfs(v); } }}