首页 > 其他 > 详细

最大疯子树

时间:2018-03-21 10:55:09      阅读:171      评论:0      收藏:0      [点我收藏+]

技术分享图片

这道题由于考场上基本上口胡出来了,就贴个代码吧。
考场没有写出来的原因是因为最后找答案的姿势不够清奇啊~~~


#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct lpl{
    int data, num;
    bool operator < (const lpl &a)const{
        return data < a.data;
    } 
}lin[maxn];
int n, a, b, ans, w[maxn], lpd[maxn];
vector<int> point[maxn];

inline void connect(int aaa, int bbb)
{
    point[aaa].push_back(bbb); point[bbb].push_back(aaa); 
}

inline void workk()
{
    memset(lpd, 0, sizeof(lpd));
    for(int i = n; i >= 1; --i)
    {
        lpd[i] += 1;
        for(int t = point[i].size() - 1; t >= 0; --t)
        {
            int now = point[i][t];
            if(i > now)
            {
                lpd[now] += lpd[i];
            }
        }
    }
    for(int i = 1; i <= n; ++i) ans = max(ans, lpd[i]);
}

int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; ++i) point[i].clear();
        for(int i = 1; i <= n; ++i) scanf("%d", &lin[i].data), lin[i].num = i;
        sort(lin + 1, lin + 1 + n);
        for(int i = 1; i <= n; ++i) w[lin[i].num] = i;
        for(int i = 1; i < n; ++i) scanf("%d%d", &a, &b), connect(w[a], w[b]);
        ans = 0; workk(); printf("%d\n", ans);
    }
    return 0;
}

最大疯子树

原文:https://www.cnblogs.com/LLppdd/p/8615218.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!