首页 > 代码库 > GDFZOJ 美丽树
GDFZOJ 美丽树
题意:
给出一棵有n个点的树,边是有向边,定义一棵美丽子树为:一个点及其子树所有点的编号恰好为一段连续的数字则称之为美丽,现在求有多少棵美丽子树?
题解:
一段连续的数字必定有一个最大的数字和最小的数字,如果现在知道最大和最小的数是什么了,判断是否连续就可以通过找出数的个数了。。
所以需要找出:一棵子树的最大值,最小值,节点个数
代码:
#include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 7; int n, c[N], r[N], root, ans, siz[N], mini[N], maxi[N]; vector <int> e[N]; void DFS (int u) { siz[u] = 1, mini[u] = u, maxi[u] = u; for (int it = 0; it < e[u].size(); ++it) { int v = e[u][it]; DFS (v); mini[u] = min (mini[u], mini[v]); maxi[u] = max (maxi[u], maxi[v]); siz[u] += siz[v]; } } int main () { scanf ("%d", &n); for (int i = 1; i < n; ++i) { int u, v; scanf ("%d%d", &u, &v); e[u].push_back(v); c[u]++, r[v]++; } for (int i = 1; i <= n; ++i) if (r[i] == 0) root = i; DFS (root); int ans = 0; for (int i = 1; i <= n; ++i) if (maxi[i] - mini[i] + 1 == siz[i]) ++ans; cout << ans << endl; return 0; }
总结:
第一眼看这个题真的是被水淹没,不知所措,但是根据极端情况切入会简单很多QAQ
GDFZOJ 美丽树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。