登录—专业IT笔试面试备考平台_牛客网
题意:
思路:
这个虽然是树形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 longusing 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;
}