首页 > 代码库 > codevs 1814 最长链
codevs 1814 最长链
二次联通门 : codevs 1814 最长链
/* codevs 1814 最长链 树形DP 当前点(LQZ)的最大价值由他的 左儿子(HKD) 和 右儿子(SYL)的最大价值转移而来 其余细节乱搞一下就可 我还是水的很开心啦.. */ #include <cstdio> #define Max 100080 inline int max (int a, int b) { return a > b ? a : b; } void read (int &now) { now = 0; register char word = getchar (); while (word > ‘9‘ || word < ‘0‘) word = getchar (); while (word >= ‘0‘ && word <= ‘9‘) { now = now * 10 + word - ‘0‘; word = getchar (); } } struct Tree_Type { int Left_Child; int Right_Child; }; Tree_Type tree[Max]; int dp[Max]; int number[Max]; int Answer; void Dfs (int now) { dp[now] = 1; if (tree[now].Left_Child == 0 && tree[now].Right_Child == 0) return ; if (tree[now].Left_Child) Dfs (tree[now].Left_Child); if (tree[now].Right_Child) Dfs (tree[now].Right_Child); dp[now] = max (dp[tree[now].Left_Child], dp[tree[now].Right_Child]) + 1; Answer = max (Answer, dp[tree[now].Left_Child] + dp[tree[now].Right_Child] + 1); } int N; int main (int argc, char *argv[]) { read (N); int x, y; for (register int i = 1; i <= N; i++) { read (x); read (y); tree[i].Left_Child = x; tree[i].Right_Child = y; } Dfs (1); printf ("%d", Answer - 1); return 0; }
codevs 1814 最长链
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。