2018牛课暑假多校第二场E-tree（链dp）

￡神魔★判官ぃ 2022-05-18 02:06 169阅读 0赞

[传送门][Link 1]

这个题自我感觉DP超级难想，并且第一次遇到这样使用DP的题。

大体思路就是先对于每个节点的子树进行dp， ![dp\[i\]\[j\]][dp_i_j]值就是与i节点连通的大小为j 的所有乘积和，j的取值1,2、、、9,10 。

分三种操作

第一种修改i节点，就需要修改从i节点开始10以内的祖先，  具体做法就是先断开， 再修改， 再连接

第二种修改父亲， 先断开，连接该节点断开的祖先，断开将要连接的节点的祖先，连接祖先即该点

第三种查询。因为i节点只是从子节点dp过来，父节点的值并没有加上，则需要将dp链反过来dp一下，然后再倒回去。

说的很抽象，需要看一下代码整理整理思路。

#include<bits/stdc++.h>
    using namespace std;
    const int mo=1e9+7;
    const int N=1e6+10;
    typedef long long ll;
    int n, m, f[N];
    ll val[N], dp[N][15];
     
    void add(int a, int b){//连接操作
        if(!a||!b) return;
        for(int i=10; i>1; i--){
            for(int j=1; j<i; j++)
                dp[a][i]=(dp[a][i]+dp[a][j]*dp[b][i-j])%mo;
        }
    }
     
    void sub(int a, int b){//断开操作
        if(!a||!b) return;
        for(int i=2; i<=10; i++){
            for(int j=1; j<i; j++)
                dp[a][i]=(dp[a][i]-dp[a][j]*dp[b][i-j]+mo)%mo;
        }
    }
     
    ll inver(ll x, ll y){
        ll ans=1;
        while(y){
            if(y&1)
                ans=ans*x%mo;
            x=x*x%mo;
            y>>=1;
        }
        return ans;
    }
     
    int main()
    {
     
        scanf("%d%d", &n, &m);
        for(int i=1; i<=n; i++)
            scanf("%lld", &val[i]), dp[i][1]=val[i];
     
        for(int i=2; i<=n; i++)
            scanf("%d", &f[i]);
     
        for(int i=n; i>1; i--)//就是这个地方不太明白，为什么是从n到2
            add(f[i], i);
     
            while(m--)
            {
                int p, x, y;
                int fa[15];
                scanf("%d%d%d", &p, &x, &y);
                for(int i=1, t=x; i<=10; i++, t=f[t]){
                    fa[i]=t;
                }
                if(p==0)
                {
                    for(int i=10; i>1; i--)
                        sub(fa[i], fa[i-1]);
                    ll inv=inver(val[x], mo-2);
                    for(int i=1; i<=10; i++)
                        dp[x][i]=dp[x][i]*inv%mo*y%mo;
                    val[x]=ll(y);
                    for(int i=2; i<=10; i++)
                        add(fa[i], fa[i-1]);
                }
                else if(p==1)
                {
                    for(int i=10; i>1; i--)
                        sub(fa[i], fa[i-1]);
                    for(int i=3; i<=10; i++)
                        add(fa[i], fa[i-1]);
                    f[x]=y;
                    for(int i=1, t=x; i<=10; i++, t=f[t])
                        fa[i]=t;
                    for(int i=10; i>2; i--)
                        sub(fa[i], fa[i-1]);
                    for(int i=2; i<=10; i++)
                        add(fa[i], fa[i-1]);
                }
                else if(p==2)
                {
                    for(int i=10; i>1; i--)
                        sub(fa[i], fa[i-1]);
                    for(int i=10; i>1; i--)
                        add(fa[i-1], fa[i]);
                    printf("%lld\n", (dp[x][y]+mo)%mo);
                    for(int i=2; i<=10; i++)
                        sub(fa[i-1], fa[i]);
                    for(int i=2; i<=10; i++)
                        add(fa[i], fa[i-1]);
                }
            }
     
        return 0;
    }

[Link 1]: https://www.nowcoder.com/acm/contest/140/E
[dp_i_j]: https://private.codecogs.com/gif.latex?dp%5Bi%5D%5Bj%5D