【POJ 1741】 Tree

【题目链接】

http://poj.org/problem?id=1741

【算法】

点分治

要求距离不超过k的点对个数，不妨将路径分成两类 :

1. 经过根节点 2. 不经过根节点

考虑第1类路径，不妨从根节点进行一次深度优先遍历，求出每个点与根节点的距离，将距离排序，然后用两个指针扫描一遍即可，注意要减掉多算的

然后，递归地计算子节点的第一类路径，即可

但是这样是会超时的，我们不妨每次选择子树的重心进行计算

这样做法的时间复杂度存在上界 : O(Nlog^2N)

【代码】

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXN 10010

int i,n,k,tot,len,ans,root,u,v,w;

int head[MAXN],weight[MAXN],size[MAXN],d[MAXN],dep[MAXN];

bool visited[MAXN];

struct Edge

{

    int to,w,nxt;

} e[MAXN<<];

inline void addedge(int u,int v,int w)

{

    tot++;

    e[tot] = (Edge){v,w,head[u]};

    head[u] = tot;

}

inline void get_root(int u,int fa,int total)

{

    int i,v;

    size[u] = ;

    weight[u] = ;

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        if (v != fa && !visited[v])

        {

            get_root(v,u,total);

            size[u] += size[v];

            weight[u] = max(weight[u],size[v]);

        }

    }

    weight[u] = max(weight[u],total-size[u]);

    if (weight[u] < weight[root]) root = u;

}

inline void dfs(int u,int fa)

{

    int i,v,w;

    d[++len] = dep[u];

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        w = e[i].w;

        if (!visited[v] && v != fa)

        {

            dep[v] = dep[u] + w;

            dfs(v,u);

        }

    }

}

inline int calc(int u)

{

    int i,j;

    int ret = ;

    len = ;

    dfs(u,);

    i = ; j = len;

    sort(d+,d+len+);

    while (i < j)

    {

        if (d[i] + d[j] <= k)

        {

            ret += j - i;

            i++;

        } else j--;

    }

    return ret;

}

inline void work(int u)

{

    int i,v,w;

    dep[u] = ;

    visited[u] = true;

    ans += calc(u);

    for (i = head[u]; i; i = e[i].nxt)

    {

        v = e[i].to;

        w = e[i].w;

        if (!visited[v])

        {

            dep[v] = w;

            ans -= calc(v);

            root = ;

            get_root(v,,size[v]);

            work(root);

        }

    }

}

int main()

{

    while (scanf("%d%d",&n,&k) != EOF && !(n ==  && k == ))

    {

        memset(visited,false,sizeof(visited));

        tot = ;

        for (i = ; i <= n; i++) head[i] = ;

        for (i = ; i < n; i++)

        {

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

            addedge(u,v,w);

            addedge(v,u,w);

        }

        size[] = weight[] = n;

        root = ;

        get_root(,,);

        ans = ;

        work(root);

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

    }

    return ;

}

巴特西

【POJ 1741】 Tree

最新文章

热门文章