C. Friends

时间：2021-07-13 04:14:21

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. 【BO】SAP BO相关问题汇总贴

    本文将以往写过的关于SAP BO相关问题的帖子汇总了一下,方便寻找 #1 为WEBI报表添加自定义字体font #2 WEBI文件打开时提示Illegal access错误 #3 安装BO服务器时,o ...

  2. &lbrack;转&rsqb;Worksheet&period;Change Event &lpar;Excel&rpar;

    本文转自:https://msdn.microsoft.com/en-us/library/office/ff839775.aspx#AboutContributor Example   The fo ...

  3. AO创建IFeature的两种方法

    原文地址:http://www.cnblogs.com/MyLucifer/archive/2010/12/01/1893212.html 在ArcGIS Resouce Center中,ESRI介绍 ...

  4. C&num; 异步操作

    在程序中,普通的方法是单线程的.但中途如果有大型的操作,比如读取大文件,大批量操作数据库,网络传输等,都会导致程序阻塞,表现在界面上就是程序卡或者死掉,界面元素不动了,不响应了.C#异步调用很好的解决 ...

  5. c3p0数据源定义

    <!-- c3p0 connection pool configuration --> <bean id="testDataSource" class=&quot ...

  6. Android自定义日历，可以点击、标注日期、节气、旧历等

    1. [图片] 9A59974C-47D4-47E3-8136-3F873EB9BBDC.jpg 2. [图片] left_arrow_pre.png 3. [图片] left_arrow.png 4 ...

  7. Spring&period;Net 入门学习笔记-----one

    一. 基本概念    Spring.Net是一个轻量级的控制反转(Ioc)和面向切面的(Aop)的容器框架: Ioc:控制反转:简单的说就是将创建对象的控制权转交给外部容器(IApplicationC ...

  8. 【XSY2843】「地底蔷薇」 NTT什么的 扩展拉格朗日反演

    题目大意 给定集合\(S\),请你求出\(n\)个点的"所有极大点双连通分量的大小都在\(S\)内"的不同简单无向连通图的个数对\(998244353\)取模的结果. \(n\le ...

  9. STS中poem&period;xml配置文件

    <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/20 ...

  10. Redis 初次见面

    目录 Redis 特性 使用场景 初次使用 安装(Linux) 配置 启动 redis 的 3 种方法 使用 redis 客户端 关闭 redis 服务 Redis 版本说明 引用 1 Redis 特 ...

相关文章