Codeforces 1032F Vasya and Maximum Matching dp
우선 완벽하게 일치하는 상황에서만 방안 수가 유일하다는 것을 관찰할 수 있다.
dp[i] [0], dp[i] [1], dp[i] 각각 표시
이 나무에 대해 0: 위로 연결하지 않기 완성1: 위로 연결하기 완성2: 위로 연결하기 미완성 방안수
#include
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair
#define PLI pair
#define PII pair
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int N = 3e5 + 7;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1);
template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;}
template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;}
template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;}
template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;}
int n;
vector<int> G[N];
LL power(LL a, LL b) {
LL ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod; b >>= 1;
}
return ans;
}
LL dp[N][3];
void go(int u, int fa) {
int pos = -1;
for(int i = 0; i < SZ(G[u]); i++) {
if(G[u][i] == fa) {
pos = i;
continue;
}
go(G[u][i], u);
}
if(~pos) {
swap(G[u][pos], G[u][SZ(G[u]) - 1]);
G[u].pop_back();
}
}
void dfs(int u) {
dp[u][0] = 1;
dp[u][1] = 0;
dp[u][2] = 1;
if(!SZ(G[u])) return;
for(auto& v : G[u]) dfs(v);
int cnts = SZ(G[u]);
vector prefix[3];
for(int i = 0; i < 3; i++) {
prefix[i].resize(cnts);
for(int j = 0; j < cnts; j++) {
int v = G[u][j];
if(!j) prefix[i][j] = dp[v][i];
else prefix[i][j] = prefix[i][j - 1] * dp[v][i] % mod;
}
}
vector prefix01(cnts);
vector suffix01(cnts);
for(int i = 0; i < cnts; i++) {
int v = G[u][i];
if(!i) prefix01[i] = (dp[v][0] + dp[v][1]) % mod;
else prefix01[i] = prefix01[i - 1] * (dp[v][0] + dp[v][1]) % mod;
}
for(int i = cnts - 1; i >= 0; i--) {
int v = G[u][i];
if(i == cnts - 1) suffix01[i] = (dp[v][0] + dp[v][1]) % mod;
else suffix01[i] = suffix01[i + 1] * (dp[v][0] + dp[v][1]) % mod;
}
// 0: 1: 2:
dp[u][0] = prefix[0][cnts - 1];
for(int i = 0; i < cnts; i++) {
int v = G[u][i];
LL tmp = dp[v][2];
if(i - 1 >= 0) tmp = tmp * prefix01[i - 1] % mod;
if(i + 1 < cnts) tmp = tmp * suffix01[i + 1] % mod;
add(dp[u][0], tmp);
add(dp[u][1], tmp);
}
dp[u][2] = prefix01[cnts - 1];
}
int main() {
scanf("%d", &n);
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
go(1, 0);
dfs(1);
printf("%lld
", dp[1][0]);
return 0;
}
/*
*/
전재 대상:https://www.cnblogs.com/CJLHY/p/10820814.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.