洛谷 P2700 逐个击破 题解【树形DP】

点击量：113

    不小心想到树链剖分去了就再也没有想过树形DP。。。不过很久没做过树形DP的题了

目录

题目背景

三大战役的平津战场上，傅作义集团在以北平、天津为中心，东起唐山西至张家口的铁路线上摆起子一字长蛇阵，并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌不让其逃走，毛泽东制定了先切断敌人东西两头退路然后再逐个歼灭敌人的战略方针。秉承伟大军事家的战略思想，作为一个有智慧的军长你，遇到了一个类似的战场局面。

 

题目描述

现在有N个城市，其中K个被敌方军团占领了，N个城市间有N-1条公路相连，破坏其中某条公路的代价是已知的，现在，告诉你K个敌方军团所在的城市，以及所有公路破坏的代价，请你算出花费最少的代价将这K个地方军团互相隔离开，以便第二步逐个击破敌人。

 

输入输出格式

输入格式：

第一行包含两个正整数n和k。

 

第二行包含k个整数，表示哪个城市被敌军占领。

 

接下来n-1行，每行包含三个正整数a,b,c，表示从a城市到b城市有一条公路，以及破坏的代价c。城市的编号从0开始。

 

输出格式：

输出一行一个整数，表示最少花费的代价。

 

输入输出样例

输入样例#1：

5 3
1 2 4
1 0 4
1 3 8
2 1 1
2 4 3

输出样例#1：

4

说明

【数据范围】

10%的数据：2≤n≤10；

 

100%的数据：2≤n≤100000，2≤k≤n，1≤c≤1000000。

题解：

    一开始以为要树剖+单点修改，然后打了半天树状数组发现是维护min，接着敲线段树。后来发现树剖这样贪心是错的。于是考试交了暴力MLE？可能是回溯没处理好

    正解是树形DP，因为是一棵树，所以每条边都是割边，那么我们就割最必要的边。对于一棵树来说，如果他有很多个儿子，就要把这些儿子里的战争点在下面就隔开，至少要在这条边上隔开。不过分析一下可以发现，如果有k个儿子，且自己不是战争点，那么只用隔k-1个儿子就可以了。因为有一个儿子可以选择在上面割还是在下面割，只要额外用一个数组g[]把这条可以延伸上去的链存一下就可以了。

    不过选哪个儿子就要做决策了。因为我们要代价最小，所以我们隔最小的k-1条边，把最大的一条留下来延伸上去，与子树根的那条边中的最小值作为这棵子树的割边值。于是在上面的DP过程中，隔开这棵子树的代价就是这条“割边”的代价。而割链可以一直延伸上去，直到碰到一棵子树的根节点为战争点。这时战争点的儿子必须全部割掉，子树的割边代价就只能由根节点上面的边来决定了。

    这就是DP的过程。不过要注意，一棵子树如果没有战争点，它就不用代价，这个在更新上去时一般不会影响，只要初始化赋值为0即可。

Code：

#include<cstdio>
#include<cstring>
int min(int x,int y)
{
    return x<y?x:y;
}
struct edge
{
    int n;
    long long v;
    int nxt;
    edge(int n,long long v,int nxt)
    {
        this->n=n;
        this->v=v;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[210000];
int head[101000],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,v,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,v,head[to]);
    head[to]=ecnt;
}

int r[100000];
long long f[100000],g[100000];
int fa[100000];
void dfs(int x)
{
    int tmp=-1;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=e[fa[x]].n)
        {
            fa[e[i].n]=(i^1);
            dfs(e[i].n);
            if(tmp==-1||g[tmp]<g[e[i].n])//算出代价最大的儿子
                tmp=e[i].n;
        }
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=e[fa[x]].n)
            f[x]+=f[e[i].n]+(e[i].n==tmp?0:g[e[i].n]);//代价最大的儿子不用加上那条链，但是要转移原本的状态

    if(r[x])//如果是战争点就要更新
    {
        g[x]=e[fa[x]].v;
        f[x]+=g[tmp];
    }
    else//如果不是更新最小代价
        g[x]=min(e[fa[x]].v,tmp==-1?0:g[tmp]);
}


int main()
{
    memset(head,-1,sizeof(head));
    int n,k,u,v,w;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d",&u);
        r[u]=1;
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
    }
    fa[0]=200000;//fa存的是边，这里指向一个空的位置
    dfs(0);
    if(r[0])
        f[0]+=g[0];
    printf("%lld\n",f[0]);
    return 0;
}