Codeforces Contest 1156 D 0-1-Tree ——树形DP

本文主要是介绍Codeforces Contest 1156 D 0-1-Tree ——树形DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

给你一棵树，每个边都是1或者0，我们称<x,y>是有效的如果从x到y的路上如果经过1的边，那么在之后就不会经过0的边，问你有多少种有效的二元组，注意<x,y>与<y,x>是不一样的。

题解：

一眼题，几乎就是树形DP的模板。
总共大概分为4种状态:
00表示从这里开始连续的0的个数
01表示从这里开始连续的0之后连续1的个数
10表示这里开始连续的1之后连续的0的个数
11表示这里开始连续的1的个数
其它情况诸如101,010都是不合法的，那么我们就不考虑了。
那么从当前点到它儿子的边为0的时候，这4种状态的变换规则：
00->+=1这个就是连续的0的数量+1
01->+=11将所有之后连续的11转变成01
10和11的数量都变成0
这样状态转移方程就写出来了，接下来计算答案：
x表示当前位置，ne表示儿子的位置
0表示00,1表示01,2表示10,3表示11，那么首先
$ans+=dp[ne][0]\ast (1+dp[x][0])\ast 2;$表示新的儿子与父亲+别的儿子的连续的00的情况数
$ans+=dp[ne][3]\ast (1+dp[x][3])\ast 2;$表示新的儿子与父亲+别的儿子的连续的11的情况数
$ans+=dp[ne][0]\ast dp[x][1];$表示新的儿子为00，到别的儿子为01的情况数
。。。
其它也就类似。
最后有两个要注意的点：

		ans+=dp[ne][1];//01ans+=dp[ne][2];//10

表示父亲到这个儿子的01后面的1的情况数和儿子的0到父亲的1的情况数。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+5;
ll dp[N][5];//[0]:00,[1]:01,[2]:10,[3]:11
ll ans;
struct node
{int to,next,w;
}e[N*2];
int head[N],cnt;
void add(int x,int y,int w)
{e[cnt].to=y;e[cnt].next=head[x];e[cnt].w=w;head[x]=cnt++;
}
void dfs(int x,int fa)
{for(int i=head[x];~i;i=e[i].next){int ne=e[i].to;if(ne==fa)continue;dfs(ne,x);int oo,zz,zo,oz;if(e[i].w==0)dp[ne][0]+=1,dp[ne][1]+=dp[ne][3],dp[ne][2]=0,dp[ne][3]=0;elsedp[ne][3]+=1,dp[ne][2]+=dp[ne][0],dp[ne][0]=dp[ne][1]=0;ans+=dp[ne][0]*(1+dp[x][0])*2;//00+00ans+=dp[ne][3]*(1+dp[x][3])*2;//11+11ans+=dp[ne][0]*dp[x][1];//00+01ans+=dp[ne][1]*dp[x][0];//01+00ans+=dp[ne][2]*dp[x][3];//10+11ans+=dp[ne][3]*dp[x][2];//11+10ans+=dp[ne][0]*dp[x][3];//00+11ans+=dp[ne][3]*dp[x][0];//11+00ans+=dp[ne][1];//01ans+=dp[ne][2];//10dp[x][0]+=dp[ne][0],dp[x][1]+=dp[ne][1],dp[x][2]+=dp[ne][2],dp[x][3]+=dp[ne][3];}}
int main()
{int n,x,y,w;memset(head,-1,sizeof(head));scanf("%d",&n);for(int i=1;i<n;i++)scanf("%d%d%d",&x,&y,&w),add(x,y,w),add(y,x,w);dfs(1,0);printf("%lld\n",ans);return 0;
}

这篇关于Codeforces Contest 1156 D 0-1-Tree ——树形DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---