TopCoder SRM 581 Div1 500 TreeUnion

一个环肯定是由两棵树中的边与中间连接的两条边组成的

那么我们就可以用 c[0/1][k] c [ 0 / 1 ] [ k ] 表示两棵树中长度为 k k 的链的数量

最后的期望就是

c[0][i]×c[1][K−2−i]×2×(n−2)!n!c[0][i]×c[1][K−2−i]×2×(n−2)!n!

#include <bits/stdc++.h>
using namespace std;
const int N=;
const int M=N<<;
int n;
int f[][N][N];
int c[][N];

template<class T> void checkmin(T &a,const T &b) { if (b<a) a=b; } 
template<class T> void checkmax(T &a,const T &b) { if (b>a) a=b; }

class TreeUnion {
public:
    double expectedCycles( vector <string> tree1, vector <string> tree2, int K ) ;
};

inline void add(int t,int x,int y){
    f[t][x][y]=f[t][y][x]=;
}

double TreeUnion::expectedCycles(vector <string> tree1, vector <string> tree2, int K) {
    memset(f,,sizeof f);
    string s;for(int i=;i<tree1.size();i++) s+=tree1[i];
    stringstream s1;
    s1<<s;
    int x;
    while(s1>>x) add(,x,++n);
    s="";for(int i=;i<tree2.size();i++) s+=tree2[i];
    stringstream s2;
    s2<<s;
    for(int i=;i<=n;i++) s2>>x,add(,x,i);
    cout<<n<<endl;
    n++;

    K-=;
    for(int i=;i<n;i++) f[][i][i]=f[][i][i]=;
    for(int o=;o<;o++)
     for(int i=;i<n;i++)
      for(int j=;j<n;j++)
       for(int k=;k<n;k++)
        f[o][j][k]=min(f[o][j][k],f[o][j][i]+f[o][i][k]);
    for(int o=;o<;o++)
     for(int i=;i<n;i++)
      for(int j=i;j<n;j++)
       c[o][f[o][i][j]]++;
    double ans=;
    for(int i=;i<K;i++)
     ans+=L*c[][i]*c[][K-i];
    ans=ans*/n/(n-);
    return ans;
}