2019ICPC-Shenyang

Posted on | In | Views:

D. Fish eating fruit

题意

将树上任意两点之间的距离按取模 $3$ 分类，分别求出三种情况的路径和

题解

  • 解法1:

    $dp1[u][j]$ 表示以 $u$ 为根节点的树，树上任意两点之间的距离取模 $3$ 为 $j$ 的路径和

    $dp2[u][j]$ 表示以 $u$ 为根节点的树，树上的点到 $u$ 的距离取模 $3$ 为 $j$ 的路径和

    $dp3[u][j]$ 表示以 $u$ 为根节点的树，树上的点到 $u$ 的距离取模 $3$ 为 $j$ 的节点数

  • 解法2:

    根据模 3 的余数设计 dp 方程

    $dp[i][k]$ 统计距 i 模 3 为 k 的子节点的数目

    $fp[i][k]$ 统计距 i 模 3 为 k 的非子节点的数目（父节点，兄弟节点，兄弟节点 的子节点）

    $ans[i][k]$ 统计距 i 模 3 为 k 的子节点到 i 的距离和

    $fans[i][k]$ 统计距 i 模 3 为 k 的非子节点距离和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
ll dp1[N][3],dp2[N][3],dp3[N][3];
vector<pii> node[N];
int n;
void dfs(int u,int fa){
    dp3[u][0]=1;
    for(auto i:node[u]){
        int v=i.fi,w=i.se;
        if(v==fa)continue;
        dfs(v,u);
        for0(i,3)dp1[u][i]=(dp1[u][i]+dp1[v][i])%mod;
        for0(i,3)
        for0(j,3){
            int tm=(i+j+w)%3;
            dp1[u][tm]=(dp1[u][tm]+dp2[u][i]*dp3[v][j]%mod+dp2[v][j]*dp3[u][i]%mod+dp3[v][j]*dp3[u][i]%mod*w%mod)%mod;
        }
        for0(i,3)dp2[u][(w+i)%3]=(dp2[u][(w+i)%3]+dp2[v][i]+w*dp3[v][i])%mod;
        for0(i,3)dp3[u][(w+i)%3]=(dp3[u][(w+i)%3]+dp3[v][i])%mod;
    }
    return ;
}
int main() {
    int u,v,w;
    while(~in(n)){
        for0(i,n){
            node[i].clear();
            mem0(dp1[i]);mem0(dp2[i]);mem0(dp3[i]);
        }
        for0(i,n-1){
            in(u,v,w);
            node[u].push_back(pii(v,w));
            node[v].push_back(pii(u,w));
        }
        dfs(0,-1);
        for0(i,3)dp1[0][i]=dp1[0][i]*2%mod;
        out0(dp1[0],3);
    }
    return 0;
}

题意

题解

代码

1
2