P3574 [POI2014]FAR-FarmCraft(贪心)

· · 题解

题意:https://www.luogu.org/problem/P3574

$f[x]=max(f[x],f[y]+size[x]+1)$($size[x]$存的是走完y之前的子树后回到$x$的时间)($+1$是从$x$到$y$的花费) 但是这样f的取值和遍历子树的顺序有关,于是考虑贪心 对于两个相邻(遍历时)的子树$y$和$z$,$y$前,$z$后 不交换: $f[x]=max(f[x],size[x]+max(f[y],f[z]+size[y]+2)+1)

交换:

f[x]=max(f[x],size[x]+max(f[z],f[y]+size[z]+2)+1)

如果交换比不交换优:

max(f[z],f[y]+size[z]+2)<max(f[y],f[z]+size[y]+2)

由于f[z]<f[z]+size[y]+2,f[y]<f[y]+size[z]+2

所以上式即为:

f[y]+size[z]\not{+\not2}<f[z]+size[y]\not{+\not2}

转化一下即为:size[z]-f[z]<size[y]-f[y]

排序即可

注意最后和size[1]+val[1]取max

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000010;
int n,cnt;
int val[maxn],head[maxn],f[maxn],size[maxn],tmp[maxn];
struct edge
{
    int to,nxt;
}e[maxn<<1];
inline bool cmp(int x,int y){return size[x]-f[x]<size[y]-f[y];}
inline void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}
void dfs(int x,int fa)
{
    if(x!=1)f[x]=val[x];
    for(int i=head[x];i;i=e[i].nxt)if(e[i].to!=fa)dfs(e[i].to,x); 
    int tot=0;
    for(int i=head[x];i;i=e[i].nxt)if(e[i].to!=fa)tmp[++tot]=e[i].to;
    sort(tmp+1,tmp+tot+1,cmp);
    for(int i=1;i<=tot;i++)f[x]=max(f[x],f[tmp[i]]+size[x]+1),size[x]+=size[tmp[i]]+2;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    printf("%d",max(f[1],size[1]+val[1]));
    return 0;
}