Flash

Description

给你一颗树，需要把每个点染色，每个点染色时间为\(t_i\)，要求同时染色的点的集合为树的独立集，最小化染色结束时间之和。

其实题面蛮有趣的♂

HINT

\(n\le 2000,t\)为整数

---

靠想象力吧，而且感觉这个题可以再优化优化状态之类的..

要先猜出一个结论，保证最优解的情况下每个点开始染色时间集合是有限的，具体的，这个集合大小为\(O(n)\)，即每个点为根的到其他每个点路径上的点权和。

然后一个树形dp就行了

\(dp_{i,j}\)代表子树\(i\)以时间\(j\)开始的最小值

从儿子转移的时候，分两种，一种儿子在它后面染，一种在前面染，分别维护一下前缀最大or最小值，然后二分一下就可以了。

---

Code:

#include <cstdio>

#include <algorithm>

#define ll long long

const int N=2010;

int head[N],to[N<<1],Next[N<<1],cnt;

void add(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

using std::min;

const ll inf=1ll<<45;

ll dis[N][N],fpre[N][N],fsuc[N][N],dp[N][N],cost[N];

int n;

void dfs1(int now,int fa,ll *dis)

{

    dis[now]=dis[fa]+cost[now];

    for(int v,i=head[now];i;i=Next[i])

        if((v=to[i])!=fa)

            dfs1(v,now,dis);

}

void dfs(int now,int fa)

{

    for(int i=1;i<=n;i++) dp[now][i]=dis[now][i];

    for(int v,i=head[now];i;i=Next[i])

        if((v=to[i])!=fa)

        {

            dfs(v,now);

            for(int j=1;j<=n;j++)

            {

                ll mi=inf;

                mi=min(mi,fpre[v][std::upper_bound(dis[v]+1,dis[v]+1+n,dis[now][j]-cost[now])-dis[v]-1]);

                mi=min(mi,fsuc[v][std::lower_bound(dis[v]+1,dis[v]+1+n,dis[now][j]+cost[v])-dis[v]]);

                if(mi<inf&&dp[now][j]!=inf) dp[now][j]+=mi;

                else dp[now][j]=inf;

            }

        }

    fpre[now][0]=fsuc[now][n+1]=inf;

    for(int i=1;i<=n;i++) fpre[now][i]=min(fpre[now][i-1],dp[now][i]);

    for(int i=n;i;i--) fsuc[now][i]=min(fsuc[now][i+1],dp[now][i]);

}

int main()

{

    scanf("%d",&n);

    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("%lld",cost+i);

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

    {

        dfs1(i,0,dis[i]);

        std::sort(dis[i]+1,dis[i]+1+n);

    }

    dfs(1,0);

    printf("%lld\n",fpre[1][n]);

    return 0;

}

---

2019.1.5