2019沈阳网赛树形dp

https://nanti.jisuanke.com/t/41403

2019沈阳网络赛D题

树形dp。一棵树，求任意两个点的距离之和。u-v和v-u算两次。两点之间的距离分为三类，模3等于0,1,2三类，最后输出这三类的总和。

第一种方法。直接累加。遍历到一个点的时候。先计算答案。答案加上所有已经遍历过得点到他的距离之和。同时该点也要加上这个值，同时要加上数量。每次先搜到底统计往下遍历的值，然后回溯的时候统计

回溯的值。因为每次只计算了之前的点到他的距离之和，所以最后的结果要乘以2，因为u-v与v-u算两次。

每次加的时候先计算当前点前一个点到他的距离，及0+该边的边权。然后在按0,1,2来累加，如果为零表示没有，就不累加。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 1e4 + ;

const int mod = 1e9 + ;

typedef pair<int, ll> pii;

int n;

vector<pii> g[N];

ll ans[];//结果数组

struct Node {

    ll valup[];//递归回溯的时候

    ll valdown[];//递归往下的时候

    ll cntdown[], cntup[];//递归往下与回溯的点数量。

} node[N];

void dfs(int u, int f) {

    int len = g[u].size();

    for(int i = ; i < len; i++) {

        int v = g[u][i].first;

        ll w = g[u][i].second;

        if(v == f) continue;

        node[v].valdown[w%] = (node[v].valdown[w%] + w) % mod;

        node[v].cntdown[w%] = (node[v].cntdown[w%] + ) % mod;

        ans[w%] = (ans[w%] + w) % mod;

        for(int j = ; j < ; j++) {

            ll ww = (node[u].valdown[j] + node[u].valup[j]) % mod;

            ll cnt = (node[u].cntdown[j] + node[u].cntup[j]) % mod;

            if(ww == ) continue;

            ll mo = (j + w) % ;

            node[v].valdown[mo] = (node[v].valdown[mo] + ww) % mod;

            node[v].valdown[mo] = (node[v].valdown[mo] + w * cnt) % mod;

            node[v].cntdown[mo] = (node[v].cntdown[mo] + cnt) % mod;

            ans[mo] = (ans[mo] + ww) % mod;

            ans[mo] = (ans[mo] + w * cnt) % mod;

        }

        dfs(v, u);

        node[u].valup[w%] = (node[u].valup[w%] + w) % mod;

        node[u].cntup[w%] = (node[u].cntup[w%] + ) % mod;

        for(int j = ; j < ; j++) {

            ll ww = node[v].valup[j];

            ll cnt = node[v].cntup[j];

            if(ww == ) continue;

            ll mo = (j + w) % ;

            node[u].valup[mo] = (node[u].valup[mo] + ww) % mod;

            node[u].valup[mo] = (node[u].valup[mo] + w * cnt) % mod;

            node[u].cntup[mo] = (node[u].cntup[mo] + cnt) % mod;

        }

    }

}

int main() {

    while(~scanf("%d", &n)) {

        int u, v;

        ll w;

        ans[] = ans[] = ans[] = ;

        for(int i = ; i < n; i++) {

            g[i].clear();

            for(int j = ; j < ; j++) node[i].valup[j] = node[i].valdown[j] = node[i].cntdown[j] = node[i].cntup[j] = ;

        }

        for(int i = ; i < n; i++) {

            scanf("%d%d%lld", &u, &v, &w);

            g[u].push_back(pii(v, w));

            g[v].push_back(pii(u, w));

        }

        dfs(, -);

        for(int i = ; i < ; i++) {

            printf("%lld%c", (ans[i] * ) % mod, i ==  ? '\n' : ' ');

        }

    }

    return ;

}

算贡献的方法。

#include <stdio.h>

#include <string.h>

using namespace std;

#define LL long long

const int N=;

const LL MOD = 1e9 + ;

int n,root;

int nex[N],tot,fir[N],to[N],len[N];

LL f[N][],g[N][],num[N][];

void build(int x,int y,int z)

{

    nex[++tot]=fir[x];

    fir[x]=tot;

    to[tot]=y;

    len[tot]=z;

}

void mo(LL &x) {

    x %= MOD;

    if(x < ) x += MOD;

}

void dfs(int x,int fa)

{

    num[x][]++;

    for(int i=fir[x];i;i=nex[i])

    {

        int y=to[i];

        if(y==fa)continue;

        dfs(y,x);

        for(int j=;j<;++j){

            g[x][(j+len[i])%]+=(num[y][j]*len[i]+g[y][j]) % MOD;

            num[x][(j+len[i])%]+=num[y][j];

            f[x][j] += f[y][j];

            mo(num[x][(j+len[i])%]);

            mo(g[x][(j + len[i]) % ]);

            mo(f[x][j]);

        }

    }

    for(int i=;i<;i++)

    {

        f[x][i]+=g[x][i];

        mo(f[x][i]);

    }

    for(int i=fir[x];i;i=nex[i])

    {

        int y=to[i];

        if(y==fa)continue;

        for(int j=;j<;++j) {

            int ind = (j-len[i])%;

            if(ind < ) ind += ;

            for(int k=;k<;++k) {

                f[x][(j+k+len[i])%]+=len[i]*(num[x][j]-num[y][ind]) % MOD *num[y][k] % MOD ;

                f[x][(j+k+len[i])%]+=(g[x][j] - g[y][ind] - num[y][ind] * len[i]) % MOD *num[y][k] % MOD ;

                f[x][(j+k+len[i])%]+=(num[x][j]-num[y][ind])*g[y][k] % MOD;

                mo(f[x][(j+k+len[i])%]);

            }

        }

    }

}

int main()

{

//    freopen("a.in","r",stdin);

    int n;

    while (~scanf("%d",&n)) {

        tot=;

        memset(fir,,sizeof(fir));

        memset(f,,sizeof(f));

        memset(g,,sizeof(g));

        memset(num,,sizeof(num));

        for (int i = ;i < n;i++) {

            int x,y,z;

            scanf("%d%d%d",&x,&y,&z);

            x++;y++;

            build(x,y,z);

            build(y,x,z);

        }

        dfs(,);

        printf("%lld %lld %lld\n",f[][],f[][],f[][]);

    }

    return ;

}

/**

3

0 1 2

0 2 3

*/

巴特西

2019沈阳网赛树形dp

最新文章

热门文章