menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DFS树+线性基+复杂度分析]UOJ138(UER #3)【开学前的涂鸦】题解
apps UOJ
local_offer 查看标签
comment 0 条评论

题目概述

原来有 $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;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up