Vijos p1688 病毒传递树形DP

https://vijos.org/p/1688

看了下别人讨论的题解才想到的，不过方法和他的不同，感觉它的是错的。（感觉、感觉）

首先N只有1000，如果能做到暴力枚举每一个节点，然后O（N）算出其贡献，那么也在允许的时间内。

假设我们现在对1这个节点进行计数，设dp[i]表示入侵i号节点和其所有子树所需要的最小时间。

那么、假设1号有k个儿子，dp[son1] 、 dp[son2]、 dp[sonk]都算出来了，那么dp[1] = max(dp[son])对吧。

但是入侵这些儿子都有一定的规矩，就是每一秒只能入侵一个，那么总是有一些儿子是最后才入侵的，就是要隔k秒后（最坏情况）才入侵这个儿子，

所以把所有儿子的权值排序，要使得max值最小，那么dp[son]值最小的，我们最后才入侵

dp[son1] += k

dp[son2] += k - 1

dp[son3] += k - 2

......

这样是最优的。

然后这一个过程时间是O(nlogn)

也能接受。

注意的是输出的时候id要按小到大输出，不然wa9

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

const int maxn = 1e3 + ;

struct Edge {

    int u, v, tonext;

}e[maxn * ];

int first[maxn], num;

void addEdge(int u, int v) {

    ++num;

    e[num].u = u, e[num].v = v, e[num].tonext = first[u];

    first[u] = num;

}

int dp[maxn];

vector<int>vc[maxn];

int dfs(int cur, int fa) {

    int son = ;

    vc[cur].clear();

    for (int i = first[cur]; i; i = e[i].tonext) {

        int v = e[i].v;

        if (fa == v) continue;

        son++;

        vc[cur].push_back(dfs(v, cur));

    }

    if (vc[cur].size() == ) return ;

    sort(vc[cur].begin(), vc[cur].end());

    for (int i = ; i < vc[cur].size(); ++i) {

        vc[cur][i] += son;

        son--;

    }

    sort(vc[cur].begin(), vc[cur].end());

    return vc[cur].back();

}

struct Node {

    int val, id;

    Node(int _val, int _id) {

        val = _val, id = _id;

    }

    bool operator < (const struct Node & rhs) const {

        if (val != rhs.val) return val < rhs.val;

        else return id < rhs.id;

    }

};

vector<struct Node>res;

void work() {

    num = ;

    memset(first, , sizeof first);

    int n;

    scanf("%d", &n);

    int root = ;

    for (int i = ; i <= n; ++i) {

        int fa;

        scanf("%d", &fa);

        addEdge(fa, i);

        addEdge(i, fa);

    }

    for (int i = ; i <= n; ++i) {

        res.push_back(Node(dfs(i, ) + , i));

    }

//    for (int i = 0; i <= n - 1; ++i) {

//        cout << res[i] << endl;

//    }

    sort(res.begin(), res.end());

    int mi = res[].val;

    printf("%d\n", mi);

    for (int i = ; i < res.size(); ++i) {

        if (mi == res[i].val) {

            printf("%d ", res[i].id);

        } else break;

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

Vijos p1688 病毒传递树形DP

最新文章

热门文章

巴特西

Vijos p1688 病毒传递 树形DP

最新文章

热门文章

Vijos p1688 病毒传递树形DP