首页 > 树上行走
开通博客写题解
头像 __故人__
发表于 2020-09-21 14:53:32
分析 其实如果一条边链接了两个颜色不一样的节点，其实这个边根本没有任何意义，因为你从任意方向都不可能进入这条边，那么我们只需要用并查集维护集合数量就可以了。 代码 #include<bits/stdc++.h> using namespace std; int read() { 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 Dear㉿You
发表于 2020-09-29 09:57:58
J 树上行走 分析 似乎有一种方法是并查集。但是这里提供一种新的思路。先画个图。 首先我们可以在第一次dfs的时候求出对于以1为根的某棵子树内部有多少相连的颜色一样的点 inline void dfs(int u,int v) { sum[u]=1; for (int i=h 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 秃头小白
发表于 2020-09-22 11:24:28
题目链接 https://ac.nowcoder.com/acm/contest/7412/J 题目大意 挺明了的吧。 解题思路 并查集！挺明显的吧。连通的区域属于一个整体，这种类型就用并查集。 如果不知道并查集，看看这个于本题而言，S1：把相同类型结点之间的边join一下，不同类型结点之间即使有边 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 肖先生~
发表于 2020-09-29 11:49:19
树上行走 题目描述 牛牛苦练武功绝学——轻功水上漂，最终没有练成，但是他学会了在树上行走的本领。 这天，牛牛落入了敌人的陷阱，身后有巨石追击，面前有n个点，n-1条边连成一张连通图（一棵树），现在牛牛必须立马选择进入这张图中，但是牛牛发现，这张图有两种不同的点，一旦进入一个点，所有与该点不 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 灯又烬
发表于 2020-09-20 11:10:30
题意 在树上存在n个点，每个点为两种状态之一，两种状态的点之间无法相互抵达，求树上最大的可联通子树，并按递增顺序输出所有节点，若有多棵子树最大，将所有子树节点均排序输出。 题解 对树进行dfs，每次求一颗子树大小，并将其所有节点标记，遍历过程记录子树个数与其所有节点，最后找到最大联通子树将所有最大子 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 AB-IN
发表于 2020-10-08 18:56:30
J 树上行走 并查集，将连边的点连起来，将连边的点连起来，写一个循环让它们的根，再通过这个根的最大值，找它的子节点。 用的出题人大佬的板 #include<bits/stdc++.h> using namespace std; typedef long long ll; const i 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”