題目鏈接

5 41 2 31 3 11 4 23 5 10 0
Sample Output
8
Source
LouTiancheng@POJ

論文題：論文傳送門

題意：

題解

參考博客：傳送門

每次分治，我們首先算出重心，為了計算重心，需要進行兩次dfs，第一次把以每個結點為根的子樹大小求出來，第二次是從這些結點中找重心

找到重心后，需要統計所有結點到重心的距離，看其中有多少對小于等于K，這里采用的方法就是把所有的距離存在一個數組里，進行快速排序，這是nlogn的，然后用一個經典的相向搜索O(n)時間內解決。但是這些求出來滿足小于等于K的里面只有那些路徑經過重心的點對才是有效的，也就是說在同一顆子樹上的肯定不算數的，所以對每顆子樹，把子樹內部的滿足條件的點對減去。

最后的復雜度是n logn logn    其中每次快排是nlogn 而遞歸的深度為logn

注意這里求重心和以往不同，因為每次分治都要對一棵子樹求重心，所以這棵樹的大小不定，所以要兩次dfs。詳細操作見代碼。

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=10000+100;int head[maxn],vis[maxn],dis[maxn];struct edge{    int to,next,w;}e[maxn*2];   //int tol=0;void add(int u,int v,int w){    e[++tol].to=v,e[tol].next=head[u],e[tol].w=w,head[u]=tol;}int root,mi,num;int mx[maxn];int ans=0;int n,k;int tn;int sz[maxn];void dfssize(int u,int f)   //處理子樹大小{    sz[u]=1;mx[u]=0;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(v==f||vis[v]) continue;        dfssize(v,u);        sz[u]+=sz[v];        if(sz[v]>mx[u]) mx[u]=sz[u];    }}void dfsroot(int r,int u,int f)    //求重心{    if(sz[r]-sz[u]>mx[u]) mx[u]=sz[r]-sz[u];    if(mi>mx[u])    {        mi=mx[u];        root=u;    }    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]||v==f) continue;        dfsroot(r,v,u);    }}void getdis(int u,int f,int d)//求距離{    dis[num++]=d;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]||v==f) continue;        getdis(v,u,d+e[i].w);    }}int cal(int u,int d){    int res=0;    num=0;    getdis(u,-1,d);    sort(dis,dis+num);    int i=0,j=num-1;    while(i<j)  //求u為根子樹中有多少對滿足條件    {        while(i<j&&dis[i]+dis[j]>k) j--;        res+=j-i;        i++;    }    return res;}void dfs(int u){    mi=inf;    dfssize(u,-1);       //這一步和下面的一步求出重心    dfsroot(u,u,-1);    ans+=cal(root,0);    vis[root]=1;         //將這個根處理完后打上標記“去掉”    for(int i=head[root];i;i=e[i].next)    {        int v=e[i].to;        if(vis[v]) continue;        ans-=cal(v,e[i].w);        dfs(v);    }}int main(){    while(~scanf("%d%d",&n,&k))    {        if(n==0&&k==0) break;        tol=0;ans=0;        memset(head,0,sizeof(head));        memset(sz,0,sizeof(sz));        memset(vis,0,sizeof(vis));        memset(dis,0,sizeof(dis));        rep(i,1,n)        {            int u,v,w;            scanf("%d%d%d",&u,&v,&w);            add(u,v,w),add(v,u,w);        }        dfs(1);        printf("%d/n",ans);    }    return 0;}