题目概述

原来有 $n​$ 个点的一棵树，现在加进了 $K​$ 条边。问多少种方案删边使得图依然连通。

解题报告

非正解警告……接下来要讲的是原题解中的算法七，不过这个解法能艹标程（度教rank1，翰爷rank2，Orz）。

图中删边让我们想到DZY Loves Chinese II，我们可以给新加进来的边随机个权值（或者直接给 $2^i​$ ，由于 $K​$ 小，这样可以保证不会出错），处理出每条边被新边覆盖的权值异或和。由于不能出现线性相关，所以每种权值只能选或不选，那么爆枚每种权值选不选，做线性基判断是否线性相关（可以剪枝），如果合法就统计答案。

但是权值可能有 $n​$ 种，这不就凉了？实际上只要考虑这 $K​$ 条边有关的点建出来的虚树（只有 $4K​$ 个点），虚树上的边对应的路径权值肯定相同，所以最多只有 $4K​$ 种不同的权值。

但是 $4K$ 好像有点崩？能不能想办法搞少点？如果所有新加进来的边都是返祖边的话，虚树节点就只有 $3K$ 个了，这样权值也会减少到 $3K$（证明在后面）。仔细一想发现新加的边实际上和原来的树边没有任何区别……所以可以随便拿一棵DFS树出来，这样非树边就都是返祖边了。

那么复杂度是 $O(2^{3K}K)​$ ，显然过不了……但是因为线性相关那道剪枝非常强力，就跑得飞快QAQ。

2019.3.1UPD：法老提供了一种证法，在非树边 $(x,y),dep_x>dep_y$ 的 $x$ 后面加一个儿子 $y'$ ，然后把非树边改成 $(y',y)$ ，这样再做虚树，点数依然是 $3K$ ，但是不需要统计非树边的边权（非树边的边权一定在新加的边中出现过），所以边权数量就是 $3K$ 。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxk=10,maxm=maxn+maxk,MOD=998244353;

int n,m,K,fa[maxn+5],val[maxm+5],cnt[maxm+5],ans;bool vis[maxn+5];
int E,lnk[maxn+5],frm[(maxm<<1)+5],son[(maxm<<1)+5],nxt[(maxm<<1)+5];
struct data {int s[maxk+5];} S;

#define Add(x,y) (son[E]=(y),frm[E]=(x),nxt[E]=lnk[x],lnk[x]=E++)
void Dfs(int x,int pre=-1){
    for (int j=(vis[x]=true,fa[x]=pre,lnk[x]);~j;j=nxt[j])
        if ((j^1)!=pre) if (!vis[son[j]]) Dfs(son[j],j);
            else if (!val[j>>1]) for (int k=(K++,j);k!=fa[son[j]];k=fa[frm[k]]) val[k>>1]^=1<<K-1;
}
inline bool Insert(data &a,int x){
    for (int j=maxk;~j&&x;j--)
        if (x>>j&1) if (!a.s[j]) return a.s[j]=x,true; else x^=a.s[j];return false;
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
void Solve(int st,data s,int now=1){
    if (st>m) return AMOD(ans,now);Solve(st+1,s,now);if (!Insert(s,val[st])) return;
    Solve(st+1,s,(LL)now*cnt[st]%MOD);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&m);m+=n-1;memset(lnk,255,sizeof(lnk));
    for (int i=0,x,y;i<m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);Dfs(1);sort(val,val+m);
    int tem=m;cnt[m=0]=1;for (int i=1;i<tem;i++) val[i]>val[i-1]?(val[++m]=val[i],cnt[m]=1):cnt[m]++;
    Solve(0,S);printf("%d\n",ans);return 0;
}