题意

给两个图，其中一个是树，问你有多少种对应方式，使得树的那个是另外一个的子图

题解

这题我是真的没什么思路TAT
如果我们直接搞，会出现多个点对应同一个点的情况
那怎么办呢？
考虑容斥
就是减去至少有一个重复，加上至少有两个重复。。。。。
然后就可以了时间复杂度$O(n^3*2^n)$
CODE:

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=520;
bool mp[N][N];
int n,m;
struct qq
{int x,y,last;
}e[N];int num,last[20];
qq E[N];int Num,Last[20];
void init (int x,int y){num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;}
void Init (int x,int y){Num++;E[Num].x=x;E[Num].y=y;E[Num].last=Last[x];Last[x]=Num;}
int a[N],cnt=0;//有哪些可以用 
LL f[20][20];
void dfs (int x,int fa)
{for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==fa) continue;dfs(y,x);}for (int u=1;u<=cnt;u++)//他用哪一个 {f[x][u]=1;for (int i=last[x];i!=-1;i=e[i].last){LL now=0;//有多少种可能int y=e[i].y;if (y==fa) continue;for (int j=Last[u];j!=-1;j=E[j].last)now=now+f[y][E[j].y];f[x][u]*=now;if (f[x][u]==0) break;}}
}
int main()
{num=0;memset(last,-1,sizeof(last));memset(mp,false,sizeof(mp));scanf("%d%d",&n,&m);for (int u=1;u<=m;u++){int x,y;scanf("%d%d",&x,&y);mp[x][y]=mp[y][x]=true;}for (int u=1;u<n;u++){int x,y;scanf("%d%d",&x,&y);init(x,y);init(y,x);}int lalal=(1<<n)-1;LL ans=0;for (int u=lalal;u>=1;u--)//枚举子集{int x=u;cnt=0;for (int i=1;i<=n;i++){if (x&1) a[++cnt]=i;x>>=1;if (x==0) break;}Num=0;memset(Last,-1,sizeof(Last));for (int i=1;i<=cnt;i++)for (int j=i+1;j<=cnt;j++)if (mp[a[i]][a[j]])Init(i,j),Init(j,i);memset(f,0,sizeof(f));dfs(1,0);LL now=0;for (int i=1;i<=cnt;i++) now=now+f[1][i];    if(((n-cnt)&1)==0) ans=ans+now;else ans=ans-now;}printf("%lld\n",ans);return 0;
}