POJ 1741 Tree 树的分治

原题链接：http://poj.org/problem?id=1741

题意：

给你棵树，询问有多少点对，使得这条路径上的权值和小于K

题解：

就。。大约就是树的分治

代码：

#include<iostream>

#include<climits>

#include<cstring>

#include<queue>

#include<algorithm>

#include<vector>

#include<cstdio>

#define MAX_N 10004

using namespace std;

struct edge{

public:

    int to,length;

    edge(int t,int l):to(t),length(l){}

    edge(){}

};

int N,K;

vector<edge> G[MAX_N];

bool centroid[MAX_N];

int subtree_size[MAX_N];

int ans;

int compute_subtree_size(int v,int p){

    int c=;

    for(int i=;i<G[v].size();i++){

        int w=G[v][i].to;

        if(w==p||centroid[w])continue;

        c+=compute_subtree_size(G[v][i].to,v);

    }

    subtree_size[v]=c;

    return c;

}

pair<int,int> search_centroid(int v,int p,int t){

    pair<int,int> res=make_pair(INT_MAX,-);

    int s=,m=;

    for(int i=;i<G[v].size();i++){

        int w=G[v][i].to;

        if(w==p||centroid[w])continue;

        res=min(res,search_centroid(w,v,t));

        m=max(m,subtree_size[w]);

        s+=subtree_size[w];

    }

    m=max(m,t-s);

    res=min(res,make_pair(m,v));

    return res;

}

void enumeratr_paths(int v,int p,int d,vector<int> &ds){

    ds.push_back(d);

    for(int i=;i<G[v].size();i++){

        int w=G[v][i].to;

        if(w==p||centroid[w])continue;

        enumeratr_paths(w,v,d+G[v][i].length,ds);

    }

}

int count_pairs(vector<int> &ds){

    int res=;

    sort(ds.begin(),ds.end());

    int j=ds.size();

    for(int i=;i<ds.size();i++){

        while(j>&&ds[i]+ds[j-]>K)--j;

        res+=j-(j>i?:);

    }

    return res/;

}

void solve_subproblem(int v){

    compute_subtree_size(v,-);

    int s=search_centroid(v,-,subtree_size[v]).second;

    centroid[s]=;

    for(int i=;i<G[s].size();i++){

        if(centroid[G[s][i].to])continue;

        solve_subproblem(G[s][i].to);

    }

    vector<int> ds;

    ds.push_back();

    for(int i=;i<G[s].size();i++){

        if(centroid[G[s][i].to])continue;

        vector<int> tds;

        enumeratr_paths(G[s][i].to,s,G[s][i].length,tds);

        ans-=count_pairs(tds);

        ds.insert(ds.end(),tds.begin(),tds.end());

    }

    ans+=count_pairs(ds);

    centroid[s]=false;

}

void solve(){

    ans=;

    solve_subproblem();

    printf("%d\n",ans);

}

bool input(){

    if(scanf("%d%d",&N,&K)!=||N+K==)return false;

    for(int i=;i<=N;i++)G[i].clear();

    for(int i=;i<N-;i++){

        int u,v;

        int c;

        scanf("%d%d",&u,&v);

        scanf("%d",&c);

        u--,v--;

        G[u].push_back(edge(v,c));

        G[v].push_back(edge(u,c));

    }

    return true;

}

int main(){

    while(input()){

        ans=;

        memset(subtree_size,,sizeof(subtree_size));

        memset(centroid,,sizeof(centroid));

        solve();

    }

    return ;

}