网硕互联帮助中心P4084 [USACO17DEC] Barn Painting G
题目描述
Farmer John 有一个大农场，农场上有
N
N
N 个谷仓（
1
≤
N
≤
10
5
1 \\le N \\le 10^5
1≤N≤105），其中一些已经涂色，另一些尚未涂色。Farmer John 想要为这些剩余的谷仓涂色，使得所有谷仓都被涂色，但他只有三种可用的油漆颜色。此外，他的获奖奶牛 Bessie 如果发现两个直接相连的谷仓颜色相同，会感到困惑，因此他希望确保这种情况不会发生。
保证
N
N
N 个谷仓之间的连接不会形成任何“环”。也就是说，任意两个谷仓之间最多只有一条连接路径。
Farmer John 有多少种方式可以为剩余的未涂色谷仓涂色？
输入格式
第一行包含两个整数
N
N
N 和
K
K
K（
0
≤
K
≤
N
0 \\le K \\le N
0≤K≤N），分别表示农场上的谷仓数量和已经涂色的谷仓数量。
接下来的
N
−
1
N-1
N−1 行每行包含两个整数
x
x
x 和
y
y
y（
1
≤
x
,
y
≤
N
,
x
≠
y
1 \\le x, y \\le N, x \\neq y
1≤x,y≤N,x=y），描述直接连接谷仓
x
x
x 和
y
y
y 的路径。
接下来的
K
K
K 行每行包含两个整数
b
b
b 和
c
c
c（
1
≤
b
≤
N
1 \\le b \\le N
1≤b≤N,
1
≤
c
≤
3
1 \\le c \\le 3
1≤c≤3），表示谷仓
b
b
b 已经被涂成颜色
c
c
c。
输出格式
计算为剩余谷仓涂色的有效方式数量，模
10
9
+
7
10^9 + 7
109+7，要求任何两个直接相连的谷仓颜色不同。
输入输出样例 #1
输入 #1
4 1
1 2
1 3
1 4
4 3
输出 #1
8
C++实现
#include<bits/stdc++.h>
#define maxn 200005
#define ll long long
using namespace std;
const int TT=1e9+7;
int n,x,y,lnk[maxn],nxt[maxn],son[maxn],tot,m;
ll f[maxn][3];
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=–f;ch=getchar();}
while (ch<='9'&&ch>='0') ret=ret*10+ch–'0',ch=getchar();
return ret*f;
}
inline void add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
inline void Dfs(int x,int fa){
for (int i=0;i<3;i++){
if (f[x][i]){for (int j=0;j<i;j++) f[x][j]=0;break;}
f[x][i]=1;
}
for (int i=lnk[x];i;i=nxt[i])
if (son[i]!=fa){
Dfs(son[i],x);
f[x][0]=f[x][0]*((f[son[i]][1]+f[son[i]][2])%TT)%TT;
f[x][1]=f[x][1]*((f[son[i]][0]+f[son[i]][2])%TT)%TT;
f[x][2]=f[x][2]*((f[son[i]][1]+f[son[i]][0])%TT)%TT;
}
}
int main(){
n=read(),m=read();
for (int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
for (int i=1;i<=m;i++) x=read(),y=read()–1,f[x][y]=1;
Dfs(1,0);
printf("%lld",(f[1][0]+f[1][1]+f[1][2])%TT);
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
评论前必须登录！
注册