Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

링크
A, B, C 즉 div 2 의 C, E, F 입 니 다. div 2 를 보십시오. 링크
D. Tree Elimination 제목 링크 는 n 개의 수 를 가지 고 있 습 니 다. 초기 대기 열 은 비어 있 습 니 다. 뒤쪽 n - 1 줄 마다 x, y x, y, 대표 x, y x, y x, y 사이 에 가장자리 가 있 습 니 다. 마지막 으로 하나의 나 무 를 구성 할 수 있 습 니 다. 한 변 의 두 노드 가 대기 열 에 없 으 면 그 중 하 나 를 대기 열 에 넣 을 수 있 습 니 다. 마지막 으로 몇 개의 다른 대기 열 을 얻 을 수 있 는 지 물 어 볼 수 있 습 니 다.데이터 범위 2 ≤ n ≤ 2 * 8727 ° 1 0 5 2 \ \ leq n \ \ \ leq 2 * 10 ^ 5 2 ≤ n ≤ 2 * 8727 ° 105, 1 ≤ x i, y i ≤ n 1 \ \ \ leq xi,y_i \ \ leq n 1 ≤ xi, yi ≤ n 분해 트 리 dp, d p [i] [0] dp [i] [0] dp [i] [0] dp [i] [0] 대표 i i 는 아버지 노드 와 비교 하기 전에 대열 에 가입 되 었 고, d p [i] [1] dp [i] [1] dp [i] [1] 대표 i 는 아버지 노드 와 비교 할 때 대열 에 가입 되 었 으 며, d p [i] [2] dp [i] [2] dp [i] [2] 대표 i i 는 아버지 노드 와 비교 한 후에 대열 에 가입 되 었 거나 가입 되 지 않 았 다.l 을 이 노드 로 연 결 된 하위 노드 길이, k 를 부모 노드 의 위치 로 설정 합 니 다.
d p [v] [0] dp [v] [0] dp [v] [0] 는 v 가 가 입 된 위치 (k 앞) 를 매 거 할 수 있 고, 이전의 하위 노드 는 반드시 가입 되 어야 한다. 즉, ∏ (d p [u j] [0] + d p [uj] [1]) \ prod (dp [u j] [0] + dp [u j] [1]] [1]) ∏ (dp [uj] [0] + dp [uj] [0] + dp [uj] [0] [uj] [0] [0] + dp [uj] [1]]] [2] dp [u j] [2] dp[uj] [uj] [2]] [uj]]]] [2]], 뒤의 노드 가 만족 2] 상황또는 이미 대기 열 에 있 는 0 상황 이 므 로 8719 ° (d p [u j] [0] + d p [u j] [2]) \ prod (dp [u j] [0] + dp [u j] [2]) 8719 ° (dp [uj] [0] + dp [uj] [2])
d. p [v] [1] dp [v] [1] dp [v] [1] 은 부모 노드 와 비교 할 때 대기 열 에 가입 되 기 때문에 앞의 노드 는 v 와 비교 할 때 가입 되 고 1 을 만족 시 키 거나 이미 가입 되 었 으 며 0 을 만족 시 켰 다. 즉, 8719 ° (d p [u j] [0] + d p [u j] [1]) \ \ prod (dp [u j] [0] + dp [u j] [1]) 8719 ° (dp [uj] [0] + dp [uj] [1]);뒤의 노드 는 부모 노드 가 가입 되 고 만족 2 또는 비교 전에 이미 가입 되 었 습 니 다. 만족 0, 즉 8719 ° (d p [u j] [0] + d p [u j] [2]) \ prod (dp [u j] [0] + dp [u j] [2]) 8719 ° (dp [uj] [0] + dp [uj] [2])
d p [v] [2] dp [v] [2] dp [v] [2] 부모 노드 가 추가 되 고 v 가 가입 되 는 위치 (k 후) 를 매 거 할 수 있 으 며, 이전의 하위 노드 는 반드시 가입 되 어야 한다. 즉, ∏ (d p [u j] [0] + d p [u j] [1] \ prod (dp [u j] [0]] + dp [u j] [0] + dp [u j] [1]) ∏ (dp [uj] [0] + dp [0] + dp [uj] [uj] [1]]]] [1]]]]]] \ \ \ prod [u j] [2] dp [u j] [2] [u j] [2] [2] [uj] [2] [2,뒤에 있 는 노드 가 2 상황 을 만족 시 켰 거나 이미 대기 열 에 있 는 0 상황 이 므 로 8719 (d p [u j] [0] + d p [u j] [2]] [2]] \ prod (dp [u j] [0] + dp [u j] [2]] [2]] 8719 (dp [uj] [0]] + dp [uj] [2]]] [2]]]]] \ prod (d p [v j] [0]] [0] + d p [j] [0] + d p [u j] [u j] [1]]]]]]]]]]]] [0] + p [j]] [0] + d p [u j] [u j] [1]]]]]]] [1]]]]]]]] + dp [uj] [1])
이동 공식 d p [v] [0] [0] = ∑ i = 1k (∏ j = 1 i − 1 (d p [u j] [0] + d p [u j] [1]) ∗ d p [u i] [u i] [2] ∗ ∗ j = k + 1 l (d p [u j]] [0] + d p [u j] [u j]] [2]] dp [v]]] [0]]]]] [0]]]] △ sum {i = \ \ {k {k} (\ \ prod {j = 1} ^ {i - 1} (dp[u j]]] [0] + d p [u j] [u j]] [2]]]]]] dp [v]]]]) * dp [u i] [2] * \ prod {j = k + 1} ^ {l} (dp [u j] [0] + dp [u j] [2]) dp [v] [0] = ∑ i = 1k(∏j=1i−1​(dp[uj​][0]+dp[uj​][1])∗dp[ui​][2]∗∏j=k+1l​(dp[uj​][0]+dp[uj​][2]) d p [ v ] [ 1 ] = ∏ j = 1 k ( d p [ u j ] [ 0 ] + d p [ u j ] [ 1 ] ) ∗ ∏ j = k + 1 l ( d p [ v j ] [ 0 ] + d p [ v j ] [ 2 ] ) dp[v][1]=\prod_{j=1}^k(dp[u_j][0]+dp[u_j][1])*\prod_{j=k+1}^{l}(dp[v_j][0]+dp[v_j][2]) dp[v][1]=∏j=1k​(dp[uj​][0]+dp[uj​][1])∗∏j=k+1l​(dp[vj​][0]+dp[vj​][2]) d p [ v ] [ 2 ] = ∑ i = k + 1 l ( ∏ j = 1 i − 1 ( d p [ u j ] [ 0 ] + d p [ u j ] [ 1 ] ) ∗ d p [ u i ] [ 2 ] ∗ ∏ j = k + 1 l ( d p [ u j ] [ 0 ] + d p [ u j ] [ 2 ] ) ) + ∏ i = 1 l ( d p [ u j ] [ 0 ] + d p [ u j ] [ 1 ] ) dp[v][2]=\sum_{i=k+1}^{l}(\prod_{j=1}^{i-1}(dp[u_j][0]+dp[u_j][1])*dp[u_i][2]*\prod_{j=k+1}^{l}(dp[u_j][0]+dp[u_j][2]))+\prod_{i=1}^{l}(dp[u_j][0]+dp[u_j][1]) dp[v][2]=∑i=k+1l​(∏j=1i−1​(dp[uj​][0]+dp[uj​][1])∗dp[ui​][2]∗∏j=k+1l​(dp[uj​][0]+dp[uj​][2]))+∏i=1l​(dp[uj​][0]+dp[uj​][1])
마지막 답 은 1 가입 상황 + 1 가입 되 지 않 은 경우 + 1 가입 되 지 않 은 경우 d p [1] [0] + d p [1] [1] [1] [1] dp [1] [0] + dp [1] [1] + dp [1] [1] + dp [1] [1] [1] [1] [1] dp [1] [1] [1] + dp [1] [0] + dp [1] [1] + dp [1] [1] + dp [1] [1] + dp [1] [0] + d p [1] [0] + d p [u] [1] [1] + dp [0] + p [u] [0] + [0] + dp[1] + dp [u] [1] [1]] + dp[1] [1]] [1 u] [0] + d p [u] [2] dp[u] [0] + dp [u] [2] dp [u] [0] + dp [u] [2] 의 접미사 적 구. 복잡 도 O (n) O (n) O (n)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll>v[200005];
ll dp[200005][3];
ll f[200005];
ll g[200005];
const int mod=998244353;
void dfs(int p,int u)
{
    //printf("%d %d
",p,u);
    for(auto x:v[u]){
        if(x!=p){
            dfs(u,x);
        }
    }
    //printf("%d %d
",p,u);
    int l=v[u].size()-(p?1:0);
    if(l==0){
        dp[u][0]=0;dp[u][1]=1;dp[u][2]=1;
        return;
    }
    int k=0;
    while(k<v[u].size()&&v[u][k]!=p)k++;
    int cnt=1;
    f[0]=1;
    for(int i=0;i<v[u].size();i++){
        int tmp=v[u][i];
        if(tmp==p)continue;
        f[cnt]=f[cnt-1]*(dp[tmp][0]+dp[tmp][1])%mod;
        cnt++;
    }
    cnt=l;
    g[l+1]=1;
    for(int i=v[u].size()-1;i>=0;i--){
        int tmp=v[u][i];
        if(tmp==p)continue;
        g[cnt]=g[cnt+1]*(dp[tmp][0]+dp[tmp][2])%mod;
        cnt--;
    }
    for(int i=1;i<=k;i++){
        dp[u][0]=(dp[u][0]+f[i-1]*g[i+1]%mod*dp[v[u][i-1]][2])%mod;
    }
    dp[u][1]=f[k]*g[k+1]%mod;
    for(int i=k+1;i<=l;i++){
        dp[u][2]=(dp[u][2]+f[i-1]*g[i+1]%mod*dp[v[u][i]][2])%mod;
    }
    dp[u][2]=(dp[u][2]+f[l])%mod;
}
void work()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(0,1);
    //printf("%lld %lld %lld
",dp[1][0],dp[1][1],dp[1][2]);
    printf("%lld
",(dp[1][0]+dp[1][1])%mod);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T;
    //scanf("%d",&T);
    //cin>>T;
    T=1;
    while(T--){
        work();
    }
}