[2018.10 雅礼] w 题解【树形DP】

点击量：225

    特别神奇+巧妙+玄学的树形DP，但是也很经典。

目录

题目背景

\(\frac 14\)遇到了一道水题，双完全不会做，于是去请教小\(\text{D}\)。小\(\text{D}\)看了\(0.607^2\)眼就切掉了这题，嘲讽了\(\frac 14\)一番就离开了。

 

于是，\(\frac 14\)只好来问你，这道题是这样的：

 

题目描述

有一棵\(n\)个节点的树，每条边长度为\(1\)，颜色为黑或白。

 

可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。

 

对于某些边，要求在操作结束时为某一种颜色。

 

给定每条边的初始颜色，求最小操作数，以及满足操作数最小时，最小的操作路径长度和。

 

输入输出格式

输入格式：

从文件w.in中读入数据。

 

第一行，一个正整数\(n\)。

 

接下来\(n-1\)行，每行四个整数\(a,b,c,d\)：

 

• 树中有一条边连接\(a\)和\(b\)。
• \(c=0,1\)表示初始颜色为白色、黑色。
• \(d=0,1,2\)表示最终要求为白色、要求为黑色、没有要求。

输出格式：

输出到文件w.out中。

输出一行，两个整数，表示最小操作数、操作数最小时的最小路径长度和。

输入输出样例

输入样例#1：

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

输出样例#1：

1 2

输入样例#2：

3
1 3 1 2
2 1 0 0

输出样例#2：

0 0

输入样例#3：

6
1 3 0 1
1 2 0 2
2 4 1 0
4 5 1 0
5 6 0 2

输出样例#3：

1 4

说明

样例1解释

操作路径\(\{2,1,3\}\)。

 

数据范围

保证给出的图为一棵树，有\(n\in [1,10^5]\)，\(a,b\in [1,n]\)，\(c\in \{0,1\}\)，\(d\in \{0,1,2\}\)。

\(\text{Subtask}\)	分值	\(n\le\)	其他限制
\(1\)	\(18\)	\(20\)	无
\(2\)	\(25\)	\(10^3\)	最多\(10\)条边使得\(d=2\)
\(3\)	\(23\)	$\backslash (10^5\backslash )$	保证\(a+1=b\)
\(4\)	\(1\)		保证\(d=2\)
\(5\)	\(13\)		保证\(d\not=2\)
\(6\)	\(20\)		无

题解：

    这个题首先需要知道一个贪心，我们如果拿0表示不需要翻转的路径，1表示需要翻转的路径，2表示没必要翻转的路径，那么对于没有2的链的情况，形如101101，一定只翻转需要翻转的部分。如果我们把整个区间都翻转了，实际上操作步数也是最优解3，但是没有“只翻转需要翻转的部分”在第二问上优。

    但是当两段1之间通过2连接了，那么就要考虑把两段1连起来以减小第一问的答案。这种操作就要用树形DP来做了。可以用树形DP来存\(i\)号结点到父亲的边分别是否翻转时，第一问和第二问的答案。

    不过这个题的DP思路比较神奇。我们用一个结构体来存\((a,b)\)，表示两个DP数组，翻转次数和总长，为了方便取min我重载了小于号。DP状态是由当前结点已经处理过的子树的最优情况和正在处理的子树的最优情况拼凑起来的，\(f[i][0]\)表示\(i\)到父亲的边不翻转时所构成的最优解；\(f[i][1]\)表示翻转时构成的最优解。

    我们把“翻转到父亲的边”看做是这棵子树伸出来一条链，那么如果当前正在处理的子树也可以伸出来一条链，那么此时有决策：正在处理的子树是否伸出一条链。如果不伸出，那么当前节点仍然保留之前的那条链；如果伸出，这两条链可以配对使得翻转次数\(a\)变少，就一定把它们配起来。

    如果已经处理过的子树没有伸出一条链的情况，那么正在处理的子树就可以决策是否伸出一条链让后面的子树去配对。

    因此对于每棵子树，有两种决策：第一种是决策后不伸出一条链，此时决策是当前子树配对前面的链（此时总翻转次数-1），或者前面和自己都不伸出链；第二种是决策后伸出一条链，可以是自己伸出去而前面不伸、也可以是前面伸出去而自己不伸。

    状态转移方程是：

k0=min(t0+f[i][0],dp(t1.a+f[i][1].a-1,t1.b+f[i][1].b));//i表示正在处理的子树
k1=min(t0+f[i][1],t1+f[i][0]);//t1,t0表示前面是否伸出一条链的最优情况

    其实理清兄弟节点之间的无后效性关系，就可以把这个题弄懂了。这里的无后效性关系意思是说无论伸出哪条链作为最终节点伸出去的链，都不会影响最终答案。

    然后在遍历完子树后，如果节点的父亲边必须翻转，那么只把\(f[x][1]\)转移上去，并加上一次翻转次数和翻转长度，另一个赋为inf；如果必须不翻转，那么就只转移\(f[x][0]=\min(t0,t1)\)。

    到这里这个代码长度很短的树形DP题就结束了。思路还是非常巧妙与神仙的，是一道非常好的题。（可能像异或类型的背包？？emmm）

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 1e9
using std::min;
struct edge
{
    int n,nxt,v;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[200100];
int head[100100],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],v);
    head[to]=ecnt;
}
struct dp
{
    int a,b;
    dp(int a,int b)
    {
        this->a=a;
        this->b=b;
    }
    dp(){}
    friend bool operator <(dp x,dp y)
    {
        if(x.a!=y.a)
            return x.a<y.a;
        return x.b<y.b;
    }
    friend dp operator +(dp x,dp y)
    {
        return dp(x.a+y.a,x.b+y.b);
    }

}f[100010][2];
void dfs(int x,int from)
{
    dp t0(0,0);
    dp t1(inf,inf);
    for(int i=head[x];~i;i=e[i].nxt)
        if(i!=(from^1))
        {
            dp k0,k1;
            dfs(e[i].n,i);//这里的转移同上面代码片段
            k0=min(t0+f[e[i].n][0],dp(t1.a+f[e[i].n][1].a-1,t1.b+f[e[i].n][1].b));
            k1=min(t0+f[e[i].n][1],t1+f[e[i].n][0]);
            t0=k0;
            t1=k1;
        }
    if(e[from].v!=1)//可以转移0
        f[x][0]=min(t0,t1);
    else
        f[x][0]=dp(inf,inf);
    if(e[from].v!=0)
        f[x][1]=min(dp(t0.a+1,t0.b+1),dp(t1.a,t1.b+1));//增加翻转次数和翻转长度
    else                                               //如果直接从t1转移则不用
        f[x][1]=dp(inf,inf);
}
int main()
{
    memset(head,-1,sizeof(head));
    int n,u,v,w,x;
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        scanf("%d%d%d%d",&u,&v,&w,&x);
        if(x==2)
            add(u,v,2);
        else if(w==x)
            add(u,v,0);
        else
            add(u,v,1);
    }
    dfs(1,200000);
    printf("%d %d\n",f[1][0].a,f[1][0].b);
    return 0;
}