正題

題目鏈接:https://ac.nowcoder.com/acm/contest/1100/B

---

題目大意

$n$個點的一棵樹，對于每個點求

距離該點不超過$k$的點數

每個點的權值是以該點為起點長度所有不超過$k$的路徑覆蓋該點的次數，求所有點的乘積

---

解題思路

對于第一問我們先考慮在子樹中的，$si{z}_{x,z}$表示距離該點不超過$z$的點數，有轉移$$si{z}_{x,z}=1+\sum _{x?>y}si{z}_{y,z?1}$$
然后那么我們每個點的答案我們就只需要計算$x$的祖宗節點即可，
定義$x$的第$z$代祖宗表示為$f{a}_z$，有貢獻$si{z}_{f{a}_z,k?z}?si{z}_{f{a}_{z?1},k?z?1}$

這樣我們就解決了第$1$問，考慮第$2$問

依舊先考慮子樹定義$mu{l}_{x,z}$表示距離為$z$時$x$點子樹中的值(注意不能計算$x$點，因為$x$的價值還不知道)
有$$mu{l}_{x,z}=\prod _{x?>y}(mu{l}_{y,z?1}?si{z}_{y,z?1})$$

那依舊對于每一個的子樹祖宗，有貢獻$$\frac{mu{l}_{f{a}_z,k?z}}{mu{l}_{f{a}_{z?1,k?z?1}}}$$

但是該點的值還沒有計算，我們發現對于該點的值就是它和所有往上的祖宗的$si{z}_{f{a}_z,k?z}+si{z}_{f{a}_{z?1},k?z?1}$之和，在上一問計算時計入即可。

時間復雜度$O(nk)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+100,XJQ=1e9+7; struct node{ll to,next; }a[N*2]; ll n,k,tot,ls[N],f[N],g[N],siz[N][15],mul[N][15],fa[N],num[15]; void addl(ll x,ll y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void dfs(ll x) {for(ll j=0;j<=10;j++)siz[x][j]=mul[x][j]=1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa[x]) continue;fa[y]=x;dfs(y);for(ll j=1;j<=10;j++){siz[x][j]+=siz[y][j-1];(mul[x][j]*=mul[y][j-1]*siz[y][j-1]%XJQ)%=XJQ;}} } ll power(ll x,ll b) {ll ans=1;while(b){if(b&1) ans=ans*x%XJQ;x=x*x%XJQ;b>>=1;}return ans; } void dfs2(ll x) {ll now=x,z=k;f[x]=(num[k]=siz[x][k]);while(--z&&fa[now]){f[x]+=siz[fa[now]][z]-siz[now][z-1];num[z]=f[x];now=fa[now];}if(fa[now])f[x]++;now=x;z=k;g[x]=mul[x][k]*f[x]%XJQ;while(--z&&fa[now]){(g[x]*=mul[fa[now]][z]*power(mul[now][z-1]*siz[now][z-1]%XJQ,XJQ-2)%XJQ)%=XJQ;(g[x]*=f[x]-num[z+1])%=XJQ;now=fa[now];}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa[x]) continue;dfs2(y);} } int main() {scanf("%lld%lld",&n,&k);for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}dfs(1);dfs2(1);for(ll i=1;i<=n;i++)printf("%lld ",f[i]);putchar('\n');for(ll i=1;i<=n;i++)printf("%lld ",g[i]); }

總結

以上是生活随笔為你收集整理的牛客-乃爱与城市拥挤程度【树形dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。