結果

問題 No.2214 Products on Tree
ユーザー vjudge1
提出日時 2025-10-09 16:50:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 182 ms / 3,000 ms
コード長 1,127 bytes
コンパイル時間 3,180 ms
コンパイル使用メモリ 278,324 KB
実行使用メモリ 30,208 KB
最終ジャッジ日時 2025-10-09 16:50:29
合計ジャッジ時間 8,151 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:34:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |         scanf("%lld",&n);
      |         ~~~~~^~~~~~~~~~~
main.cpp:35:25: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |         rep(i,2,n) scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
      |                    ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

diff # 

// Problem: No.2214 Products on Tree
// Contest: Yukicoder
// URL: https://yukicoder.me/problems/no/2214
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// Author: 3a51
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _rep(i,a,b) for(int i=(a);i>=(b);i--)
#define pi pair<int,int>
#define arr(a) array<int,(a)>
#define F fflush(stdout)
#define cases(_) while((_)--) solve();
using namespace std;
const int N=200005,mod=998244353;
int _=1,n,x,y,dp[N][2];
vector<int> v[N];
inline void add(int& x,int y){x=(x%mod+y%mod+mod)%mod;}
inline void dfs(int x,int fa){
	dp[x][0]=dp[x][1]=1;
	for(int& to:v[x]) if(to!=fa){
		dfs(to,x),dp[0][0]=dp[x][0],dp[0][1]=dp[x][1];
		dp[x][0]=dp[x][1]=0;
		rep(o,0,1) add(dp[x][o],dp[0][o]*dp[to][1]);
		add(dp[x][0],dp[0][0]*dp[to][0]);
		rep(o,0,1) add(dp[x][1],dp[0][o]*dp[to][1-o]);
	}
}
void solve(){
	scanf("%lld",&n);
	rep(i,2,n) scanf("%lld%lld",&x,&y),v[x].push_back(y),v[y].push_back(x);
	dfs(1,0);
	printf("%lld\n",dp[1][1]);
}
signed main(){
	// scanf("%d",&_);
	cases(_);
	return 0;
}
0