站外题WA求助
  • 板块题目总版
  • 楼主yh2023wyh
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/1/30 00:19
  • 上次更新2025/1/30 20:01:44
查看原帖
站外题WA求助
1404892
yh2023wyh楼主2025/1/30 00:19

题目链接(注意,需要有自己的牛客账号)

题目大意

小红拿到了一棵树,初始所有节点都是白色。
小红希望染红若干个节点,使得不存在两个白色节点相邻。
小红想知道,共有多少种不同的染色方案?
由于答案过大,请对 109+710^{9}+7 取模。

输入格式

第一行输入一个正整数 nn,代表节点数量。
接下来的 n1n−1 行,每行输入两个正整数 u,vu,v ,代表节点 uu 和节点 vv 有一条边连接。

数据范围

1n105,1u,vn1 \leq n \leq 10^{5},1 \leq u,v \leq n

输出描述

一个整数,代表染色的方案数。

WA代码(只WA不TLE或MLE)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define llinf 0x3f3f3f3f3f3f3f3f
#define inf 1175111725
int t,n,m,f[200007];
ll r[200007],w[200007],mod=1000000007;
vector<int>v[200007];
void C(int x){
	//cout<<x<<endl;
	f[x]=1;
	r[x]=w[x]=1;
	for(int i=0;i<v[x].size();i++){
		if(f[v[x][i]]) continue;
		C(v[x][i]);
		r[x]=(r[x]*(r[v[x][i]]+w[v[x][i]]))%mod;
		w[x]=(w[x]*r[v[x][i]])%mod;
	}
	return;
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	C(1);
	cout<<r[1]+w[1];
	return 0;
}
2025/1/30 00:19
加载中...