zjoi 小星星

题解：

dp很容易想

f[i][j][s]表示匹配到了i点 对应点为j点，状态为s 那么这样的时间复杂度为（3^n*n^2）

然后会发现这其实可以转化为可以重复利用元素的子集卷积

http://www.cnblogs.com/yinwuxiao/p/8471250.html

因为可以发现那些一定是不满足的
这样是2^n*n^3

然而本人并不怎么会调整常数。。所以就被卡常了------以后再改吧。。

还有就是空间差不多是卡着512mb的

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz [18][(1<<17)+10]
ll n,m,f[20][20],l,lim,pos[1<<17];
ll head[1000],dp[18]sz,count2[50];
struct re{
  ll a,b;
}a[1000];
void arr(ll x,ll y)
{
  a[++l].a=head[x];
  a[l].b=y;
  head[x]=l;
}
ll ff1 sz,ff2 sz,ff3 sz;
void dfs(ll x,ll fa)
{
  count2[x]=1;
  ll u=head[x];
  while (u)
  {
    ll v=a[u].b;
    if (v!=fa) dfs(v,x),count2[x]+=count2[v];
    u=a[u].a;
  }
  u=head[x];
  memset(ff1,0,sizeof(ff1));
  memset(ff3,0,sizeof(ff3));
  for (ll i=1;i<=n;i++)  ff1[i][1<<(i-1)]=1;
  for (ll i=1;i<=n;i++)  ff3[i][1<<(i-1)]=1;
  while (u)
  {
    ll v=a[u].b;
    memset(ff2,0,sizeof(ff2));
    if (v!=fa)
    {
      for (ll i=1;i<=n;i++)
      {
        for (ll j=1;j<=n;j++)
          if (f[i][j])
            for (ll k=1;k<lim;k++)
              ff2[i][k]+=dp[v][j][k];
        for (ll j=1;j<=n;j++)
          for (ll k=1;k<lim;k++)
            if (k>>(j-1)&1) ff1[i][k]+=ff1[i][k^(1<<(j-1))];
        for (ll j=1;j<=n;j++)
          for (ll k=1;k<lim;k++)
            if (k>>(j-1)&1) ff2[i][k]+=ff2[i][k^(1<<(j-1))];
        for (ll j=1;j<lim;j++) ff3[i][j]=ff2[i][j]*ff1[i][j];
        for (ll j=1;j<=n;j++)
          for (ll k=1;k<lim;k++)
            if (k>>(j-1)&1) ff3[i][k]-=ff3[i][k^(1<<(j-1))];
          for (ll k=1;k<lim;k++) ff1[i][k]=ff3[i][k];
      }
    }
    u=a[u].a;
  }
  for (ll i=1;i<=n;i++)
    for (ll j=1;j<lim;j++)
      if (pos[j]==count2[x]) 
      dp[x][i][j]=ff3[i][j];
}
int main()
{
  freopen("noip.in","r",stdin);
  freopen("noip.out","w",stdout);
  std::ios::sync_with_stdio(false);
  cin>>n>>m; lim=1<<n;
  for (int i=1;i<lim;i++)
  {
    int cnt=0;
    for (int j=1;j<=n;j++)
      if (i>>(j-1)&1) cnt++;
    pos[i]=cnt;
  }
  memset(f,0,sizeof(f));
  ll c,d;
  for (ll i=1;i<=m;i++)
  {
    cin>>c>>d; f[c][d]=1; f[d][c]=1;
  }
  for (ll i=1;i<=n-1;i++)
  {
    cin>>c>>d; arr(c,d); arr(d,c);
  }
  dfs(1,0);
  ll ans=0;
  for (ll i=1;i<=n;i++) ans+=dp[1][i][lim-1];
  cout<<ans<<endl;
}