[poj 1741]Treeツリー上の点治

タイトル:http://poj.org/problem?id=1741 Tree Time Limit：1000 MS Memory Limit：30000 K Total Submissions：16555 Acctepted：5396
Description Givivive Give Givive Greption Give Gregth(positive integer less than 1001).Define dist(u，v)=The min distance between node u and v.Give a n integer k，forevrypair( u，v)of extrexclexclinininininininininininininininindedededededededededededededededeaaaaaaaattttttttttttttttttcacacacacacacall(u))aaaaaaaaaaaaaaaaaaaaaaaaaawhich are valid for a given tree.
Input The input contains several test cases.The first line of each test case contains two integers n，k.(n==10000)The follwing n-1 line each containe integers u，v，l，which means there is.edgement。
Output For each test case output the answer on a single line.
Sample Input
5 4 1 2 3 1 3 1 1 4 3 5 1 0
Sample Output
8は意味を書きます：1株の辺に権力の木を持って、2時の間の距離がKに等しいことより小さいことを聞きます。
考え方：第一点分治。。。。dfs+列挙の複雑さn^2は受け入れられません。ツリーの特徴によってポイントを分けます。O（nlon^2）nlog nは、各サブツリーのルートを通るスキームの数を計算します。すなわち、サブツリーのnowからすべての点jまでの経路長dis[j]、＊lognのソート統計を求める。
1.各ソロ（x）については、x子樹の重心を扱うので、最大logn層（重心dfsは最大子樹ノードの個数を求めます。）
2.cal（x）は答えを統計して、x子樹の中でdis[x]+dix[y]<=Kの方案数を満たします。cal（x）で処理されているのは、異なるサブツリーを経ているのではなく、from【i】とfrom【j】が等しいかもしれないので、計算を繰り返したので、ans－cal（サブツリーx（K−＝dis【x】【サブツリーx】）の和；
コード:

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#define N 10005
using namespace std;
struct node{
    int x,y;
    node(int xx,int yy)
    {
        x=xx,y=yy;
    }
};
vector<node> lin[N];
vector<int> d;
int sz[N],f[N];//sz[x]-->x    ，f[x]-->x        ；
int n;
int rt;
int vis[N],dis[N];
int K;
int ans,size;
int aa,bb,cc;
void getrt(int x,int fa)//  *sz,*f   
{
    sz[x]=1;
    f[x]=0;
    for(int i=0;i<lin[x].size();i++)
    {
        int u=lin[x][i].x;
        if(vis[u]||u==fa) continue;
        getrt(u,x);
        sz[x]+=sz[u];
        f[x]=max(sz[u],f[x]);
    }
    f[x]=max(f[x],size-sz[x]);//! x        =max(      －f[x],f[x])
    if(f[x]<f[rt]) rt=x; 
}
void getdis(int x,int fa)//  dfs   ＋         sz[x],     size
{
    sz[x]=1;
    d.push_back(dis[x]);
    for(int i=0;i<lin[x].size();i++)
    {
        int u=lin[x][i].x;
        if(vis[u]||u==fa) continue;     
        dis[u]=dis[x]+lin[x][i].y;
        getdis(u,x);
        sz[x]+=sz[u];       
    }
}
int cal(int x,int y)
{   
    int ret=0;
    d.clear();
    dis[x]=y;
    getdis(x,0);

    sort(d.begin(),d.end());
    int l=0;
    int r=d.size()-1;
    while(l<r)
    {
        while(d[l]+d[r]>K&l<r) r--;
        ret+=r-l;
        l++;    
    }
    return ret;
}
void solve(int x)
{
    //cout<<x<<endl;
    ans+=cal(x,0);
    vis[x]=1;
    for(int i=0;i<lin[x].size();i++)
    {
        int u=lin[x][i].x;
        if(vis[u]) continue;
        ans-=cal(u,lin[x][i].y);
        f[0]=size=sz[u];//!!! getdis           
        getrt(u,rt=0);
        solve(rt);
    }

}
int main()
{
    while(scanf("%d%d",&n,&K))
    {
        if(!n&&!K) return 0;
        for(int i=1;i<=n;i++)
        {
            vis[i]=0;
            lin[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&aa,&bb,&cc);
            lin[aa].push_back(node(bb,cc));
            lin[bb].push_back(node(aa,cc)); 
        }   
        ans=0;
        f[0]=size=n;
        getrt(1,rt=0);  
        solve(rt);
        printf("%d
",ans);
    }
}