[POJ 1741]Tree

先備知識：樹重心

使用樹分治的思想，假設我們把$u$當作根結點，那麼所有路徑就分成了「經過$u$」和「不經過$u$」兩大類，其中「不經過$u$」的路徑可以透過子樹的遞迴來計算，因此我們只需考慮經過$u$的路徑

經過$u$的路徑又分成兩類：以$u$為端點、不以$u$為端點

以$u$為端點的算法：
我們可以先取得從$u$開始，所有長度$\leq K$的路徑，答案就是這種路徑的數目

不以$u$為端點的算法：($n$為目前考慮的子樹上節點的數量，因此我們有$\sum n=N$)
把上述的路徑排序一下，枚舉路徑$p$，二分搜找出有幾條路徑的長度$\leq K-p.length()$，就可以達到$O(n\log n)$的時間複雜度了，注意還要再把都在同一顆子樹的的「路徑對」扣掉，也是一樣的算法
不過......這樣雖然時間複雜度是正確的，不過在POJ上還是會TLE......
可以發現，枚舉的$p$長度會遞增，因此$K-p.length()$會遞減，具有單調性，就不用二分搜了，可以使用另一個遞減的指針達到$O(n)$的複雜度(不過總複雜度還是$O(n\log n)$，因為還有排序)

為了避免複雜度退化，每次根要選樹重心

時間複雜度：$O(N\log^{2}N)$

code:

#include<cstdio>
//#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
void assert(bool valid){if(valid)return;for(int a=0;;)a/=a;}
const int INF=2147483647;
void getmax(int &a,const int b){if(b>a)a=b;}
int N,K;
struct Edge
{
    int a,b,cost;
    Edge(){}
    Edge(const int _a,const int _b,const int _cost):a(_a),b(_b),cost(_cost){}
};
vector<Edge>EDGE;
vector<int>ET[10000];
bool VIS[10000];
int GetSize(const int u,const int fa)//pre-process size of subtree
{
    assert(!VIS[u]);
    int ans=1;
    for(int i=0;i<(int)ET[u].size();i++)
    {
        const Edge &e=EDGE[ET[u][i]];
        const int nxt=(e.a==u?e.b:e.a);
        if(nxt==fa||VIS[nxt])continue;
        ans+=GetSize(nxt,u);
    }
    return ans;
}
int FindCentroid(const int u,const int fa,const int n,int &mn,int &ans)//dfs to find best node
{
    assert(!VIS[u]);
    int sz=1,tmn=-INF;
    for(int i=0;i<(int)ET[u].size();i++)
    {
        const Edge &e=EDGE[ET[u][i]];
        const int nxt=(e.a==u?e.b:e.a);
        if(nxt==fa||VIS[nxt])continue;
        const int chsz=FindCentroid(nxt,u,n,mn,ans);
        sz+=chsz;
        getmax(tmn,chsz);
    }
    getmax(tmn,n-sz);
    if(tmn<mn)mn=tmn,ans=u;
    return sz;
}
int FindCentroid(const int source)//find the centroid of subtree contains node "source"
{
    int mn=INF,ans=-1;
    const int sz=GetSize(source,-1);
    FindCentroid(source,-1,sz,mn,ans);
    assert(ans!=-1&&mn<=sz/2);
    return ans;
}
void BuildPath(const int u,const int fa,const int plen,vector<int>&path)//get all distances from every node
{
    if(plen>K)return;
    path.push_back(plen);
    for(int i=0;i<(int)ET[u].size();i++)
    {
        const Edge &e=EDGE[ET[u][i]];
        const int nxt=(e.a==u?e.b:e.a);
        if(nxt==fa||VIS[nxt])continue;
        BuildPath(nxt,u,plen+e.cost,path);
    }
}
int SetRoot(const int root)//"root" is the centroid of the tree
{
    int ans=0;
    vector<int>path;
    for(int i=0;i<(int)ET[root].size();i++)
    {
        const Edge &e=EDGE[ET[root][i]];
        const int nxt=(e.a==root?e.b:e.a);
        if(VIS[nxt])continue;
        vector<int>tpath;
        BuildPath(nxt,root,e.cost,tpath);
        sort(tpath.begin(),tpath.end());
        for(int l=0,r=(int)tpath.size()-1;;l++)
        {
            while(r>l&&tpath[r]+tpath[l]>K)r--;
            if(r<=l)break;
            ans-=r-l;
        }
        for(int j=0;j<(int)tpath.size();j++)path.push_back(tpath[j]);
    }
//    printf("root=%d,sz=%d\n",root,(int)path.size());
    sort(path.begin(),path.end());
//    for(const int v:path)printf("%d ",v);puts(""); 
    for(int l=0,r=(int)path.size()-1;;l++)
    {
        while(r>l&&path[r]+path[l]>K)r--;
        if(r<=l)break;
        ans+=r-l;
    }
    ans+=path.size();
    VIS[root]=true;
    for(int i=0;i<(int)ET[root].size();i++)
    {
        const Edge &e=EDGE[ET[root][i]];
        const int nxt=(e.a==root?e.b:e.a);
        if(VIS[nxt])continue;
        ans+=SetRoot(FindCentroid(nxt));
    }
    return ans;
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&K)==2)
    {
        if(N==0&&K==0)break;
        for(int i=0;i<N;i++)ET[i].clear(),VIS[i]=false;
        EDGE.clear();
        for(int i=0,a,b,c;i<N-1;i++)
        {
            scanf("%d%d%d",&a,&b,&c),a--,b--;
            assert(0<=a&&a<N&&0<=b&&b<N);
            EDGE.push_back(Edge(a,b,c));
            ET[a].push_back(i),ET[b].push_back(i);
        }
        printf("%d\n",SetRoot(FindCentroid(0)));
        static int cnt=0;
        assert(cnt++<10);
    }
    return 0;
}