C. Friends

题意

对于任一点，求到此点距离不超过6的节点数。

分析

第一次dfs，形成一个以 1 为根的有向树，设 down[i][j] 为以i为根节点，距离 i 点距离不超过 j 的节点数（这些节点都是 i 的子孙节点）

第二次dfs，设 up[i][j] 以 i 为起点，距离 i 点距离不超过 j 的非子孙节点的个数，可根据 down 求得。

code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<map>

#include<algorithm>

using namespace std;

typedef pair<int, int> P;

typedef long long ll;

const int INF = 1e9;

const int MAXN = 1e5 + 10;

int up[MAXN][10], down[MAXN][10];

vector<int> G[MAXN];

void dfs1(int pre, int u)

{

    down[u][0] = 1;

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

    {

        int v = G[u][i];

        if(v == pre) continue;

        dfs1(u, v);

        for(int j = 1; j <= 6; j++) down[u][j] += down[v][j - 1];

    }

}

void dfs2(int pre, int u)

{

    up[u][0] = 1;

    if(u != pre) for(int i = 1; i <= 6; i++)

        up[u][i] += up[pre][i - 1] + down[pre][i - 1] - down[u][i > 2 ? i - 2 : 0];

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

    {

        int v = G[u][i];

        if(v != pre) dfs2(u, v);

    }

}

int main()

{

    int T, c = 1;

    scanf("%d", &T);

    while(T--)

    {

        int n;

        scanf("%d", &n);

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

        memset(up, 0, sizeof up);

        memset(down, 0, sizeof down);

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

        {

            int x, y;

            scanf("%d%d", &x, &y);

            G[x].push_back(y);

            G[y].push_back(x);

        }

        dfs1(1, 1); dfs2(1, 1);

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

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

        {

            int res = 0;

            for(int j = 1; j <= 6; j++) res += up[i][j] + down[i][j];

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

        }

    }

    return 0;

}

随机推荐

1. Apache HttpClient组件封装工具类

   package com.mengyao.spider.utils; import java.util.ArrayList;import java.util.HashMap;import java.ut ...

2. Service的基本组成

   Service与Activity的最大区别就是一有界面,一个没有界面. 如果某些程序操作很消耗时间,那么可以将这些程序定义在Service之中,这样就可以完成程序的后台运行, 其实Service就是一 ...

3. 3027 - Corporative Network（并差集）

   3027 - Corporative Network A very big corporation is developing its corporative network. In the begi ...

4. UVA 673 Parentheses Balance (栈)

   题意描述: 给出一段只包含()和[]的字符串,判断是否合法,合法输出YES,不合法输出NO 规则: 1.该串为空,则合法 2.若A合法,B合法,则AB合法 3.若A合法,则(A)和[A]均合法 解题思 ...

5. NumPy-矩阵部分

   NumPy-矩阵部分 [TOC] NumPy 简介 numpy可用来存储和处理大型矩阵,比Python自身的嵌套列表(nested list structure)结构要高效的多. 安装NumPy pi ...

6. BZOJ 3329: Xorequ [数位DP 矩阵乘法]

   3329: Xorequ 题意:\(\le n \le 10^18\)和\(\le 2^n\)中满足\(x\oplus 3x = 2x\)的解的个数,第二问模1e9+7 \(x\oplus 2x = ...

7. Gson解析Json数组

   需求:从steam官网获取英雄数据,即为Json数据,并导入到本地数据库 Json数据是这样的 { "result": { "heroes": [ { &quo ...

8. echarts饼图配置模板

   var option = { title:{ text:'完成人构成分析--申报', //标题的样式 textSytle:{ //颜色 color : '#FF0000', //粗细 // fontW ...

9. urllib2.Request 添加浏览器简单反爬 结合BeautifulSoup解析标签

10. oracle监听1067错误的处理

    一,oracle监听1067错误的处理修改oracle安装目录D:\DataBase\oracle\product\10.1.0\Db_1\NETWORK\ADMIN\下的 listener.ora和 ...