提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

2019 ICPC Asia-East Continent Final

2023-04-18 15:37:43 时间

D

考虑树形DP，记(f[u],g[u])分别为最终回到u/停在子树中的最晚第一次到达u的时间。原本以为在枚举了最后一个的情况下，遍历子树的顺序是以f升序的，（因为只有最后一个不对后面产生影响）；但实际上很假，因为在去掉最后一个后，倒数第二个也成了最后一个，那么针对最后一个的特殊情况也同样会出现。
这时候应该用经典的贪心不等式，列出最简化的情况的式子（只有两个子树）：
(min(f1,f2-2*sz1)ge min(f2,f1-2*sz2))
然后分讨，发现第二个min如果取f1必然不成立，然后取另一个就可以得到：
(f1-2*sz1 le f2-2*sz2)
然后经过一些经典的证明可以推广到整个序列，所以按照这个排序即可。

点击查看代码 
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5,inf=2e9+5+N;
void Min(int& x,int y){
    if(y<x) x=y;
}
void Max(int& x,int y){
    if(y>x) x=y;
}
int hd[N],to[N<<1],nx[N<<1],tt;
void add(int u,int v){
    nx[++tt]=hd[u];
    to[hd[u]=tt]=v;
}
int n,k,a[N],f[N],g[N],sz[N],sn[N],h[N],Mn[N],su[N];
bool cmp(int x,int y){
    return f[x]+2*sz[x]<f[y]+2*sz[y];
}
void dfs(int u,int fa){
    sz[u]=1;
    for(int e=hd[u];e;e=nx[e]) if(to[e]!=fa){
        int v=to[e];
        dfs(v,u);
        sz[u]+=sz[v];
    }
    int m=0;
    for(int e=hd[u];e;e=nx[e]) if(to[e]!=fa) sn[++m]=to[e];
    if(!m){
        f[u]=min(a[u],a[u]+k-2*(sz[u]));
        g[u]=a[u];
        return;
    }
    sort(sn+1,sn+m+1,cmp);
    f[u]=g[u]=-inf;
    for(int i=1;i<=m;i++) su[i]=su[i-1]+sz[sn[i]],h[i]=f[sn[i]]-2*su[i-1]-1;
    Mn[m+1]=inf;
    for(int i=m;i;i--) Mn[i]=min(Mn[i+1],h[i]);
    int mn=inf;
    for(int i=1;i<=m;i++){
        Max( f[u],min(h[i]-(su[m]-su[i])*2,min(Mn[i+1]+sz[sn[i]]*2,mn)) );
        Max(g[u],min( min(a[u]+k-2*(sz[u]-sz[sn[i]]),g[sn[i]]-2*(sz[u]-sz[sn[i]]-1)-1),min(Mn[i+1]+sz[sn[i]]*2,mn) ) );
        Min(mn,h[i]);
    }
    Min(f[u],min(a[u],a[u]+k-2*(sz[u])) );
    Min(g[u],a[u]);
    //printf("u=%d f=%d g=%d
",u,f[u],g[u]);
}
int main()
{
    cin>>n>>k;
    for(int u,v,i=1;i<n;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    dfs(1,0);
    if(g[1]<0) puts("-1");
    else cout<<g[1]<<endl;
    return 0;
}

相关文章