解析

關于合理的實現

這題卡在最后的小破dp是我沒想到的

一開始看到200的數據范圍就不禁笑出了聲
lca直接On求！
然后就開始大力分類討論
然后就卡在了一個問題上
兩個棧AB，分別有a和b個元素，隨機從兩個棧中彈出一個元素，求最后A棧先空的概率

我天真的認為，上面那個東西就等于$\frac{b}{a+b}$
然后樣例3就卡住了。。。

事實是一個簡單的dp即可
所以思路還是要靈通

代碼

#include<bits/stdc++.h>const int N=205; const int mod=1e9+7; #define ll long long using namespace std; inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int n,m;struct node{int to,nxt; }p[N<<1]; int fi[N],cnt; inline void addline(int x,int y){p[++cnt]=(node){y,fi[x]};fi[x]=cnt;return; }int dep[N],fa[N],lca[N][N],dis[N][N]; void dfs(int x,int f){fa[x]=f;dep[x]=dep[f]+1;for(int i=fi[x];~i;i=p[i].nxt){int to=p[i].to;if(to==f) continue;dfs(to,x);}return; } inline int Lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);while(dep[x]>dep[y]) x=fa[x];while(x!=y){x=fa[x];y=fa[y];}return x; } ll ni[N]; inline ll ksm(ll x,ll k){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; } ll f[N][N]; int main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifmemset(fi,-1,sizeof(fi));cnt=-1;n=read();for(int i=1;i<=n;i++) ni[i]=ksm(i,mod-2);for(int i=0;i<=n;i++){for(int j=1;j<=n;j++) f[i][j]=i==0?1:(f[i-1][j]+f[i][j-1])*ni[2]%mod;}for(int i=1;i<n;i++){int x=read(),y=read();addline(x,y);addline(y,x);}//fprintf(stderr,"OK\n");dfs(1,0);for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){lca[i][j]=lca[j][i]=Lca(i,j);dis[j][i]=dis[i][j]=dep[i]+dep[j]-2*dep[lca[i][j]];}}ll ans(0);for(int i=1;i<=n;i++){for(int j=1;j<i;j++){int o=lca[i][j];for(int k=1;k<=n;k++){if(k==i){(ans+=ni[n])%=mod;continue;}if(k==j) continue;int pl(0);if(dep[lca[i][k]]>dep[lca[j][k]]) pl=lca[i][k];else pl=lca[j][k];if(o==i){if(lca[i][pl]==pl) (ans+=ni[n])%=mod;else if(pl==j) continue;else{(ans+=f[dis[pl][i]][dis[pl][j]]*ni[n])%=mod;}}else if(o==j){if(lca[j][pl]==pl) continue;else if(pl==i) (ans+=ni[n])%=mod;else{//if(i==5&&j==1&&k==2) printf("%")(ans+=f[dis[pl][i]][dis[pl][j]]*ni[n])%=mod;}}else{if(dep[pl]<dep[o]) pl=o;if(pl==i) (ans+=ni[n])%=mod;else if(pl==j) continue;else{(ans+=f[dis[pl][i]][dis[pl][j]]*ni[n])%=mod;}}}}}printf("%lld\n",ans);return 0; } /*5 37 1 4 1 9 1 3 5 31 1 4 22 3 5 */ 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的CF1540B Tree Array（期望，dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

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