LG P6748 『MdOI R3』Fallen Lord

Description

L 国有 $n$

国王 L 派遣了一些军队来驻守这些道路，驻守每一条道路的军队战斗力都可以被量化为 $[1,m]$

每个城市都有一个城主，第 $i$ $$a_i$。如果国王 L 在与第 $i$ 个城市相连的所有道路上驻守的军队战斗力的中位数超过了城主的忍耐度，那么城主就会认为国王不信任他而产生谋反的心理。$

国王 L 当然不希望有人*，但他又想使驻守道路的军队的总战斗力最大来保证国防安全。现在他找到了 L 国最强的 OIer —— 您，去来帮助他解决这个问题。

如果无论如何安排军队都会有人想要*，那么输出$-1$。

注：对于任意$k$

因为对于一条边的边权，只需要关心其与两端点忍耐度的大小关系即可

所以设$f_{u,0/1}$为边$(u,fa_u)$的边权$ < /geq a_u$时$u$的子树内的最大边权和，$g_{u,0/1}$为边$(u,fa_u)$的边权$ < /geq a_{fa_u}$时$u$的子树内和边$(u,fa_u)$的最大边权和

因此有转移：

对于$f_{u,0/1}$,先选择其所有$v in son_u$的$g_{v,0/1}$，对于$f_{u,0}$，在由$g_{v,1}-g_{v,0}$组成的数列中，贪心地选择$du_u- lfloor frac{du_u}{2} floor -1 $个$ > 0$的数加入其中，同样地，对于$f_{u,1}$，在由$g_{v,1}-g_{v,0}$组成的数列中，贪心地选择$du_u- lfloor frac{du_u}{2} floor -2 $个$ > 0$的数加入其中

$$g_{u,0}=
egin{cases}
max(f_{u,0}+a_u,f_{u,1}+a_{fa_u})& a_u leq a_{fa_u}\
f_{u,0}+a_{fa_u}& a_u > a_{fa_u}
end{cases}
$$

$$g_{u,1}=
egin{cases}
f_{u,1}+m& a_u leq a_{fa_u}\
max(f_{u,0}+a_{fa_u},f_{u,1}+m)& a_u > a_{}fa_u
end{cases}
$$

当$du_u leq 2$时，$f_{u,1}=-inf$

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,m,a[500005],head[500005],tot,f[500005][2],g[500005][2],du[500005],c[500005];
struct Edge
{
    long long to,nxt;
}edge[1000005];
inline long long read()
{
    long long w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+ch-'0';
        ch=getchar();
    }
    return w*f;
}
bool cmp(long long x,long long y)
{
    return x>y;
}
void dfs(long long k,long long fa)
{
    long long lim=du[k]/2+1;
    for(long long i=head[k];i;i=edge[i].nxt)
    {
        long long v=edge[i].to;
        if(v!=fa)
        {
            dfs(v,k);
        }
    }
    c[0]=0;
    for(long long i=head[k];i;i=edge[i].nxt)
    {
        long long v=edge[i].to;
        if(v!=fa)
        {
            c[++c[0]]=g[v][1]-g[v][0];
            f[k][0]+=g[v][0];
            f[k][1]+=g[v][0];
        }
    }
    sort(c+1,c+c[0]+1,cmp);
    long long i;
    for(i=1;i<du[k]-lim&&c[i]>0;i++)
    {
        f[k][0]+=c[i];
        f[k][1]+=c[i];
    }
    if(c[i]>0&&du[k]>2)
    {
        f[k][0]+=c[i];
    }
    if(du[k]<=2)
    {
        f[k][1]=-(1<<30);
    }
    if(a[k]<=a[fa])
    {
        g[k][0]=max(f[k][0]+a[k],f[k][1]+a[fa]);
        g[k][1]=f[k][1]+m;
    }
    else
    {
        g[k][0]=f[k][0]+a[fa];
        g[k][1]=max(f[k][0]+a[k],f[k][1]+m);
    }
}
int main()
{
    n=read();
    m=read();
    for(long long i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(long long i=1;i<n;i++)
    {
        long long u=read(),v=read();
        edge[++tot]=(Edge){v,head[u]};
        head[u]=tot;
        edge[++tot]=(Edge){u,head[v]};
        head[v]=tot;
        ++du[u];
        ++du[v];
    }
    dfs(1,0);
    printf("%lld
",f[1][0]);
    return 0;
}

Fallen Lord

LG P6748 『MdOI R3』Fallen Lord

Description

Solution

相关推荐