明明空间大小没问题啊……然后试了大样例也过了
by info___tion @ 2019-04-18 13:21:12
orz
by longlongzhu123 @ 2019-04-18 13:21:14
我看看。。。等一会
by longlongzhu123 @ 2019-04-18 13:22:14
前排观望info___tion
by hyfhaha @ 2019-04-18 13:22:20
前排%$info__tion$
是不是递归爆栈了
by fmj_123 @ 2019-04-18 13:24:52
我不敢用这个账号交QAQ，我还没A，被卡常了...
试一下在主程序前return 0？如果还M就继续看看
@[info___tion](/space/show?uid=76049)
by longlongzhu123 @ 2019-04-18 13:25:03
@[info___tion](/space/show?uid=76049) 运行时MLE https://www.luogu.org/recordnew/show/18315022
main之前return 0不会M
by longlongzhu123 @ 2019-04-18 13:27:51
@[info___tion](/space/show?uid=76049) 测验完毕，递归爆栈
```cpp
#include<cstdio>
#include<cstring>
#include<cassert>
typedef long long ll;
const int maxn=18;
const int MAX_LEVEL = 1000000;
class Solution
{
public:
void solve()
{
int gcnt;scanf("%d%d",&n,&gcnt);
for(int i=1;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);--x;--y;
tmap[x][y]=tmap[y][x]=1;
}
for(int i=1;i<=gcnt;i++)
{
int x,y;scanf("%d%d",&x,&y);--x;--y;
gmap[x][y]=gmap[y][x]=1;
}
tree_dfs(0,-1,0);
ll ans=0;
for(int i=1;i<(1<<n);i++)
{
ll tmp=0;
memset(f,-1,sizeof(f));used_sz=0;
for(int j=0;(1<<j)<=i;j++) if( (1<<j)&i ) used[used_sz++]=j;
for(int j=0;j<used_sz;j++) tmp+=dfs(0,used[j],0);
if( (n-used_sz)%2==0 ) ans+=tmp;
else ans-=tmp;
}
printf("%lld\n",ans);return;
}
private:
int n;
bool gmap[maxn][maxn],tmap[maxn][maxn];
struct Edge{int from,to;}edges[maxn];int edges_sz;
int Next[maxn],Head[maxn];
int nd_sz[maxn];
void add_edge(int from,int to)
{
edges[++edges_sz]=(Edge){from,to};
Next[edges_sz]=Head[from];Head[from]=edges_sz;return;
}
void tree_dfs(int r,int fa,int level)
{
assert(level<MAX_LEVEL);
nd_sz[r]=1;
for(int i=0;i<n;i++)
{
if( i==fa or !tmap[r][i] ) continue;
add_edge(r,i);tree_dfs(i,r,level+1);nd_sz[r]+=nd_sz[i];
}
return;
}
ll f[maxn][maxn];int used[maxn],used_sz;
ll dfs(int tn,int gn,int level)
{
assert(level<MAX_LEVEL);
if( ~f[tn][gn] ) return f[tn][gn];
if( nd_sz[tn]==1 ) return 1;
f[tn][gn]=1;
for(int i=Head[tn];i;i=Next[i])
{
int tto=edges[i].to;
ll tmp=0;
for(int j=0;j<used_sz;j++)
{
int to=used[j];
if( gmap[gn][to] ) tmp+=dfs(tto,to,level+1);
}
f[tn][gn]*=tmp;
}
return f[tn][gn];
}
}SOL;
int main()
{
SOL.solve();return 0;
}
```
当场就~~断言~~了
by longlongzhu123 @ 2019-04-18 13:31:27
看看有没有什么`dfs(u, u)`之类的吧
by longlongzhu123 @ 2019-04-18 13:33:33
@[info___tion](/space/show?uid=76049) orz 您会$\mathrm{MLE}$
by disangan233 @ 2019-04-18 13:35:25