当前位置: 首页> 游戏> 评测 > 松江注册公司_小米网络营销案例分析_品牌推广网络公司_搜索引擎优化的基本内容

松江注册公司_小米网络营销案例分析_品牌推广网络公司_搜索引擎优化的基本内容

时间:2025/7/11 18:21:59来源:https://blog.csdn.net/yjfyjfyjf54188/article/details/145575386 浏览次数:0次
松江注册公司_小米网络营销案例分析_品牌推广网络公司_搜索引擎优化的基本内容

洛谷题目传送门

题目描述

Farmer John 有一个大农场,农场上有 N 个谷仓(1≤N≤100000),其中一些已经涂色,另一些尚未涂色。Farmer John 想要为这些剩余的谷仓涂色,使得所有谷仓都被涂色,但他只有三种可用的油漆颜色。此外,他的获奖奶牛 Bessie 如果发现两个直接相连的谷仓颜色相同,会感到困惑,因此他希望确保这种情况不会发生。

保证 NN 个谷仓之间的连接不会形成任何“环”。也就是说,任意两个谷仓之间最多只有一条连接路径。

Farmer John 有多少种方式可以为剩余的未涂色谷仓涂色?

输入格式

第一行包含两个整数 N 和 K(0≤K≤N),分别表示农场上的谷仓数量和已经涂色的谷仓数量。

接下来的 N−1 行每行包含两个整数 x 和 y(1≤x,y≤N,x≠y),描述直接连接谷仓 x 和 y 的路径。

接下来的 K 行每行包含两个整数 b 和 c(1≤b≤N, 1≤c≤3),表示谷仓 b 已经被涂成颜色 c。

输出格式

计算为剩余谷仓涂色的有效方式数量,模 1e9+7,要求任何两个直接相连的谷仓颜色不同。

输入输出样例

输入 #1

4 1
1 2
1 3
1 4
4 3

输出 #1

8

思路

显然是树状dp,我们令 dp[u][i] 为节点 u 染为  i 号颜色的的方案数

由定义得到 dp[u][1]=\prod_{v\epsilon son(u)} (dp[v][2]+dp[v][3])

                   dp[u][2]=\prod_{v\epsilon son(u)} (dp[v][1]+dp[v][3])

                   dp[u][3]=\prod_{v\epsilon son(u)} (dp[v][1]+dp[v][2])

对于没有染色的点,染所有颜色的方案数都为 1

对于已经染色的点,除了染的颜色方案数为 1,其余方案数都为 0

Code

#include<bits/stdc++.h>
using namespace std;
const long long N=2e5+5,mod=1e9+7;
long long tot,h[N],ne[N],to[N],a[N],n,m,dp[N][3];
void add(long long u,long long v){tot++;to[tot]=v;ne[tot]=h[u];h[u]=tot;
}
void dfs(int u,int fa){for(int i=h[u];i;i=ne[i]){int v=to[i];if(v==fa)continue;dfs(v,u);dp[u][1]=dp[u][1]*((dp[v][2]+dp[v][3])%mod)%mod;//更新结果 dp[u][2]=dp[u][2]*((dp[v][1]+dp[v][3])%mod)%mod;dp[u][3]=dp[u][3]*((dp[v][1]+dp[v][2])%mod)%mod;}
}
int main(){cin>>n>>m;int x,y;for(int i=1;i<n;i++){cin>>x>>y;add(x,y);add(y,x);}for(int i=1;i<=n;i++)dp[i][1]=dp[i][2]=dp[i][3]=1;//初始化方案数 for(int i=1;i<=m;i++){cin>>x>>y;if(y==1)dp[x][2]=dp[x][3]=0;else if(y==2)dp[x][1]=dp[x][3]=0;else dp[x][1]=dp[x][2]=0;}dfs(1,0);cout<<(dp[1][1]+dp[1][2]+dp[1][3])%mod;//分类用加法,输出结果 return 0;
}

关键字:松江注册公司_小米网络营销案例分析_品牌推广网络公司_搜索引擎优化的基本内容

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: