首先要注意到可以重新弄 \(dfs\) 树,非树边就都是返祖边了。

注意到 \(k\) 比较小,可以想到把非树边的端点作为关键点建虚树。关键点直接的缩成边,有边权 \(w_i\) 表示链长度。

缩完的图的大小最多 \(20\) 左右 。然后对于一个缩之后的图的连通子图,对答案贡献为 \(\prod_{不在子图中} w\)

这个怎么弄呢? 题解里有种比较难写的状压做法。

然而可以暴力 \(dfs\) 删边,不连通了就停下,用 DZY Loves Chinese II 这题的方法判断是否连通。

注意一下常数是可以过的… 而且实现时不需要真建的虚树,很好写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<algorithm>
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef long long LL;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<3)+(res<<1)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=100005,maxe=200105,P=998244353;
int fir[maxn],nxt[maxe],son[maxe],tot=1;
int n,m,Q,w[maxe],tag[maxn],sum[1050];
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
bool vis[maxn],used[maxe];
inline int getrdm(){
static int _t=0;
return 1<<(_t++);
}
void dfs1(int x){
vis[x]=true;
for(int j=fir[x];j;j=nxt[j])
if(!used[j>>1]){
used[j>>1]=true;
if(!vis[son[j]]) dfs1(son[j]); else{
w[j>>1]=getrdm(); sum[w[j>>1]]++;
tag[x]^=w[j>>1]; tag[son[j]]^=w[j>>1];
}
}
}
void dfs2(int x,int e_fa){
vis[x]=true;
for(int j=fir[x];j;j=nxt[j])
if(!used[j>>1]){
used[j>>1]=true;
if(!vis[son[j]]) dfs2(son[j],j), tag[x]^=tag[son[j]];
}
w[e_fa>>1]=tag[x]; sum[tag[x]]++;
}
int b[60][15];
bool Insert(int k,int x){
for(int i=9;i>=0;i--)
if((x>>i)&1){
if(!b[k][i]){ b[k][i]=x; return true; }
x^=b[k][i];
}
return false;
}
int ans,cnt;
pair<int,int> a[60];
void dfs(int stp,int val){
if(stp>cnt){
ans=(ans+val)%P;
return;
}
memcpy(b[stp],b[stp-1],sizeof(b[stp]));
dfs(stp+1,val);
if(Insert(stp,a[stp].X)) dfs(stp+1,(LL)val*a[stp].Y%P);
}
int main(){
freopen("uoj138.in","r",stdin);
freopen("uoj138.out","w",stdout);
srand(2333);
n=getint(); m=getint(); m+=n-1;
for(int i=1;i<=m;i++){
int x=getint(),y=getint();
add(x,y); add(y,x);
}
dfs1(1);
memset(vis,0,sizeof(vis));
memset(used,0,sizeof(used));
dfs2(1,0);
for(int i=1;i<=1023;i++)
if(sum[i]) a[++cnt]=mp(i,sum[i]);
dfs(1,1);
printf("%d\n",ans);
return 0;
}