【树形DP+换根思想】2022牛客多校加赛 H

àì夳堔傛蜴生んèń 2024-03-23 17:21 81阅读 0赞

[登录—专业IT笔试面试备考平台\_牛客网][IT]

题意：

![4acbe231ccfb46d99ee831d13a667218.png][]

![7cdb215a69ff404aa69a41e5e2987c48.png][]

思路：

这个虽然是树形DP，却用了换根的思想....

首先，后缀0的个数可以转化成min(cnt2,cnt5)，其中cnt2为2的因子个数，cnt5为5的因子个数

然后进行DP

设dp\[u\]\[0/1\]为，在除了u这棵子树中，2/5的因子个数

为什么要这么设计，我们发现，如果计算的结点是在子树里面的，那么lca就是u，子树的贡献直接就是sz\[u\]\*cnt\[u\]\[0/1\]

但是在这棵子树之外的贡献不能这么求，因此需要额外设计

然后转移就很简单：

dp\[v\]\[j\]=dp\[u\]\[j\]+(sz\[u\]-sz\[v\])\*cnt\[u\]\[j\]

最后统计贡献的时候加上子树部分的贡献，取min(cnt2,cnt5)就好了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=1e6+10;
    const int mxv=1e6+10;
    const int mod=998244353;
    const int Inf=1e18;
    
    vector<int> G[mxn];
    
    int N,Q;
    int u,v,x;
    int sz[mxn];
    int dp[mxn][2],cnt[mxn][2];
    
    void init(){
        for(int i=1;i<=N;i++){
            if(i%2==0){
                int t=i,s=0;
                while(t%2==0) t/=2,s++;
                cnt[i][0]=s;
            }
            if(i%5==0){
                int t=i,s=0;
                while(t%5==0) t/=5,s++;
                cnt[i][1]=s;
            }
        }
    }
    void dfs1(int u,int fa){
        sz[u]=1;
        for(auto v:G[u]){
            if(v==fa) continue;
            dfs1(v,u);
            sz[u]+=sz[v];
        }
    }
    void dfs2(int u,int fa){
        for(auto v:G[u]){
            if(v==fa) continue;
            for(int j=0;j<=1;j++){
                dp[v][j]=dp[u][j]+(sz[u]-sz[v])*cnt[u][j];
            }
            dfs2(v,u);
        }
    }
    void solve(){
        cin>>N>>Q;
        init();
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs1(1,0);
        dfs2(1,0);
        while(Q--){
            cin>>x;
            int res=1e18;
            for(int j=0;j<=1;j++){
                res=min(res,dp[x][j]+sz[x]*cnt[x][j]);
            }
            cout<<res<<'\n';
        }
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	while(__--)solve();return 0;
    }

[IT]: https://ac.nowcoder.com/acm/contest/38727/H
[4acbe231ccfb46d99ee831d13a667218.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/36554b75c51d480881e3d5db340c3934.png
[7cdb215a69ff404aa69a41e5e2987c48.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/212019f82263441cbb09360a11217e30.png