【LOJ】 #2521. 「FJOI2018」领导集团问题

题解

这道题很显然可以想出来一个\(n^2\)的dp，也就是dp[u][i]表示以u为根的子树最大值是i的点集最大是多少（i是离散化后的值）

就是对于每个儿子处理出后缀最大值然后按位相加更新父亲，我们把最大值处理成差分来存储，儿子们的最大值按位相加等于差分按位相加，后缀最大值出现了变化仅当加入了父亲节点形成一个点集，也就是父亲节点的值w[u]，所在的位置，跳过差分一串连续的0，遇到第一个有数的值，然后减掉，可以用map

代码

#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <map>

#include <queue>

//#define ivorysi

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define mo 974711

#define MAXN 200005

#define eps 1e-3

#define RG register

#define calc(x) __builtin_popcount(x)

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 + c - '0';

	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {putchar('-');x = -x;}

    if(x >= 10) {

	out(x / 10);

    }

    putchar('0' + x % 10);

}

struct node {

    int to,next;

}E[MAXN * 2];

int head[MAXN],sumE,N,w[MAXN],a[MAXN],tot;

map<int,int> dp[MAXN];

void add(int u,int v) {

    E[++sumE].to = v;E[sumE].next = head[u];head[u] = sumE;

}

void merge(int u,int v) {

    if(dp[u].size() < dp[v].size()) swap(dp[u],dp[v]);

    for(auto k : dp[v]) dp[u][k.fi] += k.se;

    dp[v].clear();

}

void dfs(int u,int fa) {

    for(int i = head[u] ; i ;i = E[i].next) {

	int v = E[i].to;

	if(v != fa) {

	    dfs(v,u);

	    merge(u,v);

	}

    }

    map<int,int>::iterator k = dp[u].begin();

    if(k->fi >= w[u]) return;

    k = dp[u].lower_bound(w[u]);--k;

    if(k->se == 1) dp[u].erase(k);else k->se -= 1;

}

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) read(w[i]),a[i] = w[i];

    sort(a + 1,a + N + 1);

    tot = unique(a + 1,a + N + 1) - a - 1;

    for(int i = 1 ; i <= N ; ++i) w[i] = lower_bound(a + 1,a + tot + 1,w[i]) - a;

    for(int i = 1 ; i <= N ; ++i) dp[i][w[i]] = 1;

    int u;

    for(int i = 2 ; i <= N ; ++i) {

	read(u);

	add(u,i);add(i,u);

    }

    dfs(1,0);

    int ans = 0;

    for(auto k : dp[1]) ans += k.se;

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

巴特西

【LOJ】 #2521. 「FJOI2018」领导集团问题

题解

代码

最新文章

热门文章