题意都需要看题解才能明白我是不是已经废了

题意就是求一个从树\(S\)到图\(T\)的映射，满足若树上的两个点有边，则它们映射在图中的两个点也连有边，且不能有多个点映射到同一个点

我们先不考虑不能有多个点映射到同一个点的限制。设\(dp[u][i]\)表示树上的\(u\)映射为图中的点\(i\)时，\(u\)的子树中合法的方案数。那么只要做一个树形dp即可，复杂度为\(O(n^3)\)

然而如果我们只是按上面那样去做，有可能会产生多个点映射到同一个点的情况。那么我们就要减去图中被映射的点只有\(n-1\)个时的情况。我们可以暴力枚举被剩下的\(n-1\)个点是哪几个，然后再做一次树形dp即可。发现有多减了\(n-2\)个点的情况...

于是不难看出这个其实就是容斥了，枚举图中被选的点，容斥处理即可

//minamoto#include
    
     #define ll long long#define rint register intusing namespace std;#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)char buf[1<<21],*p1=buf,*p2=buf;int read(){    int res,f=1;char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=25;ll dp[N][N],res=0;bool vis[N];int ban[N],mp[N][N];struct eg{int nx,v;}e[N];int head[N],tot,n,m;inline void add(int u,int v){e[++tot]={head[u],v},head[u]=tot;}void dfs(int u){    vis[u]=1;for(rint i=1;i<=n;++i)dp[u][i]=1;    for(rint i=head[u];i;i=e[i].nx){        int v=e[i].v;if(vis[v])continue;dfs(v);        for(rint j=1;j<=n;++j)if(ban[j]){            ll sum=0;            for(rint k=1;k<=n;++k)if(ban[k])sum+=dp[v][k]*mp[k][j];            dp[u][j]*=sum;        }else dp[u][j]=0;    }}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read();    for(rint i=1,u,v;i<=m;++i)u=read(),v=read(),mp[u][v]=mp[v][u]=1;    for(rint i=1,u,v;i
     
      >=1,++i)ban[i]=p&1,sz-=p&1;        dfs(1);ll ret=0;        for(rint i=1;i<=n;++i)ret+=dp[1][i];        sz&1?res-=ret:res+=ret;    }printf("%lld\n",res);return 0;}