LA 6434 The Busiest City dfs

Tree Land Kingdom is a prosperous and lively kingdom. It has N cities which are connected to each
other by roads such that there is exactly one path to go from one city to any other city. Each road in
the kingdom connects exactly two diﬀerent cities.
Every day a lot of merchants travel from one city to other cities in the kingdom making this kingdom
famous for its commerce. The king of this kingdom wonders, which city is the busiest one in his entire
kingdom. The busyness of a city is deﬁned as the number of merchants who visits this city on each
day. A merchant is considered as visiting c city if and only if city c lies on the path when the merchant
travels from city a to city b.
Unfortunately, we need a lot of resources and time to answer the king’s question. Therefore, the
ministers come up with an idea to approximate the answer so they can provide the king with an “early”
answer while they are working on the actual answer. To approximate the answer, the ministers modify
the deﬁnition of a city’s busyness a bit. The busyness of a city a is now deﬁned as the number of
diﬀerent pair of cities a − b such that c lies in a simple path from a to b (note that c is neither a nor
c). A path is considered simple if and only if it does not visit any city more than once.
Consider the example as shown in Figure 1 below.
In this example, the busyness of city A, B, E and F are 0 because there is no pair of cities which
path visits those nodes. The busyness of city C is 7 (the pairs are: A-B, A-D, A-E, A-F, B-D, B-E, B-F)
and the busyness of city D is also 7 (the pairs are: A-E, A-F, B-E, B-F, C-E, C-F, E-F). Therefore, the
highest busyness in this example is 7, which occurs in city C and D.
Given the kingdom’s road structure, your task is to determine the highest busyness among all cities
in the kingdom.
Input
The ﬁrst line of input contains an integer T (T ≤ 50) denoting the number of cases. Each case begins
with an integer N (3 ≤ N ≤ 20,000) denoting the number of cities in the kingdom. The cities are
numbered from 1 to N. The following N − 1 lines each contains two integers a and b (1 ≤ a, b ≤ N)
denoting a road which connects city a and city b.
Output
For each case, output ‘Case #X: Y ’, where X is the case number starts from 1 and Y is the highest
busyness among all cities in the kingdom for that case.
Notes:
• Explanation for 1st sample case
This sample case corresponds to Figure 1 in the problem statement.
• Explanation for 2nd sample case
The busiest city is city 2 with busyness of 1 (the pair is: 1-3).
• Explanation for 3rd sample case
The busiest city is city 2 with busyness of 3 (the pairs are: 1-3, 1-4, 3-4)

Sample Input

1 3
2 3
3 4
4 5
4 6

1 2
2 3

1 2
2 3
2 4

2 5
1 2
7 4
3 7
2 3
7 6
Sample Output
Case #1: 7
Case #2: 1
Case #3: 3
Case #4: 9

题意：给出n个顶点，n-1条边，对于每一个顶点来说每有一条路径经过，繁荣度+1，求最大繁荣度。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int  inf =0x7f7f7f7f;

const double pi=acos(-1);

const int maxn=20000+10;

int n,ans=0,sum[maxn];

vector<vector<int> > G(maxn);

void add_edge(int u,int v)

{

    G[u].push_back(v);

    G[v].push_back(u);

}

void dfs(int father,int u)

{

    for(int i=0;i<G[u].size();i++)

    {

        int v=G[u][i];

        if(v==father) continue;

        dfs(u,v);

        sum[u]+=sum[v];

    }

    int m=sum[u]*(n-1-sum[u]),tmp=0;

    for(int i=0;i<G[u].size();i++)

    {

        int x=G[u][i];

        if(x==father) continue;

        tmp+=sum[x]*(sum[u]-sum[x]);

    }

    m+=tmp/2;

    ans=max(ans,m);

    sum[u]++;

}

int main()

{

    int cas,kk=0;

    scanf("%d",&cas);

    while(cas--)

    {

        scanf("%d",&n);

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

        for(int i=1;i<=n-1;i++)

        {

            int u,v;

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

            add_edge(u,v);

        }

        MM(sum,0);ans=0;

        dfs(0,1);

        printf("Case #%d: %d\n",++kk,ans);

    }

    return 0;

}

　　分析：很棒的一道题目，刚开始还是觉得有难度的，因为想的是对于每个点在O（1）时间内统计出他左边的点的个数和右边点的个数，然后还要考虑一个点可能不止连接着两个点.......

正确解答：原先的想法中统计出点分支的边对应的子树上点的个数思路还是有些正确的，难点就在与不会怎么统计，实际上，没有充分利用好这是一棵树的性质，是一颗树的话就意味着可以以1为根节点建一棵树，

然后sum[u]代表u的子树上的节点个数，那么这个点的富有度就是sum[u]*（n-1-sum[u]）+子树上的

点，dfs建树就好，复杂度O(N);

巴特西

LA 6434 The Busiest City dfs

最新文章

热门文章