【點分治】POJ 1741 Tree

第一次寫點分治，一道入門題，稍微了解到了點分治解決的順序和大緻流程。

每次尋找目前子樹的重心，圍繞重心計算答案，這道題計算目前子樹内經過了目前重心的滿足條件的節點對數，用子樹内總的符合條件的對數減去兩個節點在同一子樹内的對數。然後繼續向子樹分治。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int bal, asize, sum, n, k, ans;

int tov[], nex[], h[], stot, w[];

void add ( int u, int v, int s ) {
    tov[++stot] = v;
    w[stot] = s;
    nex[stot] = h[u];
    h[u] = stot;
}

int siz[], vis[];

void find_root ( int u, int f ) {
    siz[u] = ;
    int res = ;
    for ( int i = h[u]; i; i = nex[i] ) {
        int v = tov[i];
        if ( v == f || vis[v] ) continue;必須要加vis條件，因為再往下分治時不能确定目前點的父親是否被周遊過（點分治是圍繞重心展開的！
        find_root ( v, u );
        siz[u] += siz[v];
        res = max ( res, siz[v] );
    }
    res = max ( res, sum - siz[u] );
    if ( res < asize ) {
        asize = res, bal = u;
    }
}

int dep[], dis[];

void get_dep ( int u, int f ) {
    dep[++dep[]] = dis[u];
    siz[u] = ;
    for ( int i = h[u]; i; i = nex[i] ) {
        int v = tov[i];
        if ( v == f || vis[v] ) continue;
        dis[v] = dis[u] + w[i];
        get_dep ( v, u );
        siz[u] += siz[v]; 
    }
}

int cal ( int u, int now ) {
    dis[u] = now; dep[] = ;
    get_dep ( u,  );
    sort ( dep + , dep + dep[] +  );
    int tmp = , l = , r = dep[];
    while ( l < r ) {
        if ( dep[l] + dep[r] <= k ) {
            tmp += r - l; l ++;///找能滿足l的r統計對數
        } else r --;
    }
    return tmp;
}

void work ( int u ) {
    ans += cal ( u,  );
    vis[u] = ;
    for ( int i = h[u]; i; i = nex[i] ) {
        int v = tov[i];
        if ( vis[v] ) continue;
        ans -= cal ( v, w[i] );
        sum = siz[v];
        asize = ;
        find_root ( v, u );
        work ( bal );
    }
}

int main ( ) {
    while ( scanf ( "%d%d", &n, &k ) ==  ) {
        if ( n ==  && k ==  ) break;
        asize = ;
        stot = ; ans = ;
        memset ( h, , sizeof ( h ) );
        memset ( dis, , sizeof ( dis ) );
        memset ( vis, , sizeof ( vis ) );
        for ( int i = ; i < n; i ++ ) {
            int a, b, c;
            scanf ( "%d%d%d", &a, &b, &c );
            add ( a, b, c );
            add ( b, a, c ); 
        }
        sum = n;
        find_root ( ,  );
        work ( bal );
        printf ( "%d\n", ans );
    }
    return ;
}