本文共 3916 字，大约阅读时间需要 13 分钟。

1、

2、题目大意：

给一棵树，dist(u,v)是指的uv两个顶点之间的最短距离，现在给出一个k值，

求在这棵树上有多少对(u,v)满足dist(u,v)<=k

如果uv在同一个分支上，那么dist(u,v)就死uv间的距离，如果uv不在同一个分支上，那么他们之间的最短距离就等于他们到最近的公共父节点的距离之和。

这道题目如果用dfs搜索每一个根节点得用n*n的时间，会超时，看介绍的需要用到分治，

3、题目

Description

Input

Output

Sample Input

5 41 2 31 3 11 4 23 5 10 0

Sample Output

8

AC代码参考

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define MAX 21000#define INF 2147483647#define max(a,b) (a)>(b)?(a):(b)#define min(a,b) (a)<(b)?(a):(b)struct node {    int v, len; //v表示邻接点，len表示边权    int sum, bal; //sum表示子孙节点个数，bal表示拆当前点后子树的最大结点数    node *next;} tree[MAX], *head[MAX], tp[MAX];int n, ptr, ans, root;int tot, k, dist[MAX], vis[MAX];int size[MAX], sign[MAX]; //size表示最大分支的结点数,sign是一个hash数组void Initial() {    ans = ptr = 0;    for (int i = 0; i < MAX; ++i)        vis[i] = 0,head[i] = NULL;}void AddEdge(int a, int b, int c) {    tree[ptr].v = b, tree[ptr].len = c;    tree[ptr].next = head[a], head[a] = &tree[ptr++];}void Dfs(int s, int pa) {    tp[s].sum = tp[s].bal = 0;    node *p = head[s];    while (p != NULL) {        if (p->v != pa && vis[p->v] == 0) {//在哪赋值成1？？？            Dfs(p->v, s);            tp[s].sum += tp[p->v].sum;                //累计子节点个数            tp[s].bal = max(tp[s].bal, tp[p->v].sum); //找最大分支        }        p = p->next;    }    tp[s].sum++;             //自己    sign[tot] = s;           //hash    size[tot++] = tp[s].bal; //记录每个最大分支的结点数}int GetRoot(int s) {    tot = 0, Dfs(s, 0);    int maxx = INF, maxi, cnt = tp[s].sum;    for (int i = 0; i < tot; ++i) {        size[i] = max(size[i], cnt - size[i]);        if (size[i] < maxx) {            maxx = size[i];            maxi = sign[i];        }    }    return maxi;}void GetDist(int s, int pa, int dis) {    //保存每个结点到根节点的距离    node *p = head[s];    dist[tot++] = dis;    while (p != NULL) {        if (p->v != pa && vis[p->v] == 0 && dis + p->len <= k)            GetDist(p->v, s, dis + p->len);        p = p->next;    }}void Count1(int s) {    sort(dist, dist + tot);    int left = 0, right = tot - 1;    while (left < right) {        if (dist[left] + dist[right] <= k)            ans += right - left, left++;        else right--;    }}void Count2(int s) {    vis[s] = 1;    node *p = head[s];    while (p != NULL) {        if (vis[p->v] == 0) {            tot = 0, GetDist(p->v, s, p->len);            sort(dist, dist + tot);            int left = 0, right = tot - 1;            while (left < right) {                if (dist[left] + dist[right] <= k)                    ans -= right - left, left++;                else right--;            }        }        p = p->next;    }}void Solve(int s, int pa) {    root = GetRoot(s);    tot = 0,GetDist(root, 0, 0);    Count1(root);    Count2(root);  // ans += count1 - coutn2;    node *p = head[root];    while (p != NULL) {        if (p->v != pa && vis[p->v] == 0)            Solve(p->v, root);        p = p->next;    }}int main(){    int i, j, a, b, c;    while (scanf("%d%d", &n, &k),n + k) {        Initial();        for (i = 1; i < n; ++i) {            scanf("%d%d%d", &a, &b, &c);            AddEdge(a, b, c);            AddEdge(b, a, c);        }        Solve(1, 0);        printf("%d\n", ans);    }}
     
    
   

转载地址：http://drddi.baihongyu.com/