Luogu4084 [USACO17DEC]Barn Painting (树形DP)
2024-10-20 21:42:29
数组越界那个RE+WA的姹紫嫣红的。。。
乘法原理求种类数,类似于没有上司的舞会。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
#define nR(a,b,c) for(register int a = (b); a >= (c); -- a)
#define Max(a,b) ((a) > (b) ? (a) : (b))
#define Min(a,b) ((a) < (b) ? (a) : (b))
#define Fill(a,b) memset(a, b, sizeof(a))
#define Abs(a) ((a) < 0 ? -(a) : (a))
#define Swap(a,b) a^=b^=a^=b
#define ll long long
#define ON_DEBUG
#ifdef ON_DEBUG
#define D_e_Line printf("\n\n----------\n\n")
#define D_e(x) cout << #x << " = " << x << endl
#define Pause() system("pause")
#define FileOpen() freopen("in.txt","r",stdin);
#else
#define D_e_Line ;
#define D_e(x) ;
#define Pause() ;
#define FileOpen() ;
#endif
struct ios{
template<typename ATP>ios& operator >> (ATP &x){
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x*= f;
return *this;
}
}io;
using namespace std;
const int N = 100007;
const int mod = 1000000007;
struct Edge{
int nxt, pre;
}e[N << 1];
int head[N], cntEdge;
inline void add(int u, int v){
e[++cntEdge] = (Edge){head[u], v}, head[u] = cntEdge;
}
int col[N];
long long f[N][3];
inline void DFS(int u, int fa){
if(col[u])
f[u][col[u] - 1] = 1;
else{
R(i,0,2)
f[u][i] = 1;
}
for(register int i = head[u]; i; i = e[i].nxt){
int v = e[i].pre;
if(v == fa) continue;
DFS(v, u);
f[u][0] = f[u][0] * (f[v][1] + f[v][2]) % mod;
f[u][1] = f[u][1] * (f[v][0] + f[v][2]) % mod;
f[u][2] = f[u][2] * (f[v][0] + f[v][1]) % mod;
}
}
int main(){
//FileOpen();
int n, K;
io >> n >> K;
R(i,2,n){
int u, v;
io >> u >> v;
add(u, v);
add(v, u);
}
R(i,1,K){
int x, nodeColor;
io >> x >> nodeColor;
col[x] = nodeColor;
}
DFS(1, 0);
printf("%lld", ((f[1][0] + f[1][1] + f[1][2]) % mod + mod) % mod);
return 0;
}
最新文章
- 微服务与Docker介绍
- Gnome_Terminal
- 【BZOJ1857】[Scoi2010]传送带 三分法
- [转]Eclipse Debug不为人知的秘密
- Android Sqlite 数据库版本更新
- C# VS JAVA 差异 (未完待续)
- asp.net 计算两个时间差
- js 中创建对象
- ArcGIS制图表达Representation-制图表达原理
- Redis全面介绍
- 高通平台的bootloader过程【转】
- Linux kernel的中断子系统之(二):IRQ Domain介绍
- Event filter with query ";SELECT * FROM __InstanceModi
- ELK大流量日志分析系统搭建
- 法嵌入互操作类型“SHDocVw.ShellWindowsClass”请改用适用的接口-解决方法
- laravel控制器方法中,用函数作为变量进行传递时的处理方法
- urllib模块学习
- PTA 7-50 畅通工程之局部最小花费问题(最小生成树Kruskal)
- 如何更方便的查看Linux内核代码的更新记录【转】
- 纪中OJ 2019.01.25【NOIP提高组】模拟 B 组 T2 数字对
热门文章
- Change Buffer 只适用于非唯一索引页?错
- H5 页面 上使用js实现一键复制功能
- 降维、特征提取与流形学习--非负矩阵分解(NMF)
- springSecurity + jwt + redis 前后端分离用户认证和授权
- ptorch常用代码梯度篇(梯度裁剪、梯度累积、冻结预训练层等)
- C语言学习之我见-memchr()内存查找字符函数
- ACM-01背包问题-Python
- 微服务探索之路04篇k8s增加子节点,metrics资源监控,ingress-nginx域名配置及https配置
- PotPlayer播放百度云盘视频
- 无语——真的好用到不行的7个Python小技巧