ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[牛客竞赛]生活在树上(图论 + 树)

2022年4月28日 954点热度 0人点赞 0条评论

题目传送门:生活在树上 (nowcoder.com)

题目描述

请看原题。

这里介绍两种思路。

思路一

将点 i 当作根,父节点、子节点都当作子节点。

只要建立一个双向边的图就可以完成。相当于先把树建立起来,再把某个点i拉出来作为根,那么这又可以形成一颗新的以i为根的树。

那么每个点能够到达的点就是每个点的孙子节点。

在输入的时间将d = 2的边直接加到答案中,d = 1的记录边,d > 2的全部忽略。

代码一(449ms)

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

inline int readInt()
{
    int s = 0, w = 1;char ch = getchar();
    for(;ch > '9' || ch < '0';ch = getchar())if(ch == '-')w = -1;
    for(;'0' <= ch && ch <= '9';ch = getchar())s = s * 10 + ch - '0';
    return s * w;
}

const int maxn = 1e6 + 10;
int ans[maxn];
vector<int> g[maxn];


signed main()
{
    ios::sync_with_stdio(0);
	int N = readInt();
    for(int i = 2;i <= N; ++ i)
    {
        int x = readInt(), w = readInt();
        if(w == 2)ans[i] ++, ans[x] ++;
        else if(w == 1)g[x].pb(i), g[i].pb(x);
    }
    for(int i = 1;i <= N; ++ i)
        for(auto j : g[i])ans[i] += g[j].size();
    
    for(int i = 1;i <= N; ++ i)printf("%lld\n",ans[i] + 1);
    return 0;
}

思路二

每个点的答案由父节点(爷爷节点)来更新,不需要记录具体有哪些子节点,只需要知道子节点的数量就好。

那么每个点i可以到达以下四种点:

  • 爷爷节点(如果存在的话),由点i来更新
  • 兄弟节点(父亲的儿子,如果存在的话)由点i来更新
  • 自己(儿子的父亲,就算没有儿子根据题意也可以到达)直接 + 1就行,如果有父节点就可以到达父节点
  • 孙子节点(如果存在的话)由孙子来更新,所以点i不用管这个

那么现在只剩下两个部分需要更新的,就是点i的爷爷和兄弟。

1.通过fa[fa[i]]来验证爷爷是否存在,若存在那么i和爷爷的答案都 + 1。

2.如果fa[i]存在,那么i的答案还要加上nson[fa[i]] - 1,也就是兄弟节点的个数。注意这里的 - 1不能和前面自身的+ 1抵消,因为父亲未必存在,但是自身不管有没有父亲都是要加上的。

代码二(244ms)

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

inline int readInt()
{
    int s = 0, w = 1;char ch = getchar();
    for(;ch > '9' || ch < '0';ch = getchar())if(ch == '-')w = -1;
    for(;'0' <= ch && ch <= '9';ch = getchar())s = s * 10 + ch - '0';
    return s * w;
}

const int maxn = 1e6 + 10;
int ans[maxn];
int fa[maxn], nson[maxn];


signed main()
{
    ios::sync_with_stdio(0);
	int N = readInt();
    for(int i = 2;i <= N; ++ i)
    {
        int x = readInt(), w = readInt();
        if(w == 2)ans[i] ++, ans[x] ++;
        else if(w == 1)fa[i] = x, nson[x] ++;
    }
    for(int i = 1;i <= N; ++ i)
    {
        if(fa[i])ans[i] += nson[fa[i]], ans[fa[i]] ++;
        if(fa[fa[i]])ans[i] ++, ans[fa[fa[i]]] ++;
    }
    for(int i = 1;i <= N; ++ i)printf("%lld\n",ans[i] + 1);
    return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 图论 树 牛客网 算法竞赛
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目描述
  • 思路一
  • 代码一(449ms)
  • 思路二
  • 代码二(244ms)

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号