首页 > 其他分享 >[NOI2023] 深搜

[NOI2023] 深搜

时间:2023-07-31 20:47:39浏览次数:43  
标签:return int res jump dep NOI2023 mod

和考试的时候思路差不多。

首先考虑钦定一部分关键点是合法的 ,带上容斥系数。

对于一条非树边,要求其在任何一个钦定点作为根的时候都不是横叉边。

具体而言,对于一个钦定点集合,我们建出钦定点集合的虚树,那么符合条件的非树边有如下几类:

不妨先考虑特殊性质 \(B\) ,没有横叉边的情况:

  • 完全在某条虚树边上

  • 从虚树上某个点向非虚树上的子树方向的边

  • 虚树根向上方的边

对于每个点,预处理第二类和第三类的边的个数,记为 \(down_x,up_x\) 。

考试的时候写的是,\(dp_{x,i}\) 表示考虑 \(x\) 子树内的点和边,选出的、覆盖当前点的上端点最浅的非树边深度是 \(i\) 的方案数,转移和 [NOI2020]命运 一模一样。

但是这样需要线段树合并,而且不太好拓展。

我们考虑设 \(dp_x\) 表示 \(x\) 为虚树上的点的方案数,对于每个子树 \(y\),如果这子树里没选点,方案数是 \(2^{down_y}\) ,否则,方案数是枚举最浅的点 \(z\),用 \(dp_y\) 乘上 \(x\to z\) 的方案数,这个可以边转移边维护。

以 \(DFS\) 序为下标开一颗线段树,\(dp_x\) 存在 \(dfn_x\) 位置。

更新就是一个区间乘法,区间求和。

现在考虑一般情况。

注意到横叉边只有跨过虚树根的才合法,且必须被虚树包含且最多涉及到两棵子树。

对于一个二维平面上的点 \((x,y)\) ,我们表示选择的两个子树最浅的点的 \(dfs\) 序分别是 \(x,y\) 的方案数,初始时是 \(dp_x\times dp_y\)。

对于每个横叉边,相当于一个矩形内的方案数乘二,最终求所有位置的和,可以离散化后做一遍扫描线解决。

复杂度 \(O(n\log n)\)

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+7;
struct edge 
{
	int y,next;
}e[2*N];
int flink[N],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=flink[x];
	flink[x]=t;
}
int n,m,K;
bool key[N];
int dep[N],st[N],ed[N],tim=0;
int jump[N][21];
int fup[N],fdown[N],tree[N],pw[N];
const int mod = 1e9+7;
vector<int> Up[N],Down[N],G[N],A[N]; 
int Jump(int x,int y)
{
	for(int k=19;k>=0;k--)
	if(jump[x][k]&&dep[jump[x][k]]>dep[y])x=jump[x][k];
	return x;
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	for(int k=19;k>=0;k--)if(dep[jump[x][k]]>=dep[y])x=jump[x][k];
	if(x==y)return x;
	for(int k=19;k>=0;k--)if(jump[x][k]!=jump[y][k]) 
	{
		x=jump[x][k];
		y=jump[y][k];
	}
	return jump[x][0];
}
void dfs(int x,int pre)
{
	jump[x][0]=pre;
	for(int k=1;jump[x][k-1];k++)jump[x][k]=jump[jump[x][k-1]][k-1]; 
	dep[x]=dep[pre]+1;
	st[x]=++tim;
	for(int i=flink[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		dfs(y,x);
	}
	ed[x]=tim;
}
inline bool Anc(int x,int y){return st[x]<=st[y]&&st[y]<=ed[x];}
int U[N],V[N];
void dfs2(int x,int pre)
{
	tree[x]=Down[x].size();
	for(int i=flink[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		dfs2(y,x);
		tree[x]+=tree[y];
		fdown[x]+=fdown[y];
	}
}
int dis[N];
inline int plu(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
struct segment 
{
	int sum[N*4],tag[N*4];
	void build(int k,int l,int r)
	{
		sum[k]=0;tag[k]=1;
		if(l==r)
		{
			sum[k]=dis[l];
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		sum[k]=plu(sum[k<<1],sum[k<<1|1]);
	}
	void pushup(int k)
	{
		sum[k]=plu(sum[k<<1],sum[k<<1|1]);
	}
	void pushtag(int k,int v)
	{
		sum[k]=1ll*sum[k]*v%mod;
		tag[k]=1ll*tag[k]*v%mod;
	}
	void pushdown(int k)
	{
		if(tag[k]^1)
		{
			pushtag(k<<1,tag[k]);
			pushtag(k<<1|1,tag[k]);
			tag[k]=1;
		}
	}
	void mul(int k,int l,int r,int L,int R,int v)
	{
		if(L<=l&&r<=R) 
		{
			pushtag(k,v);
			return;
		}
		pushdown(k);
		int mid=(l+r)>>1;
		if(L<=mid)mul(k<<1,l,mid,L,R,v);
		if(R>mid) mul(k<<1|1,mid+1,r,L,R,v);
		pushup(k);
	}
	int query(int k,int l,int r,int L,int R)
	{
		if(L>R)return 0;
		if(L<=l&&r<=R) return sum[k];
		pushdown(k);
		int mid=(l+r)>>1;
		int res=0;
		if(L<=mid)res=plu(res,query(k<<1,l,mid,L,R));
		if(R>mid) res=plu(res,query(k<<1|1,mid+1,r,L,R));
		return res;
	}
	void upd(int k,int l,int r,int x,int v)
	{
		if(l==r) 
		{
			sum[k]=v;
			return;
		}
		pushdown(k);
		int mid=(l+r)>>1;
		if(x<=mid)upd(k<<1,l,mid,x,v);
		else upd(k<<1|1,mid+1,r,x,v);
		pushup(k);
	}
}T,S;
int dp[N][4],f[4],ans=0;
int ipw[N];
const int inv2=(mod+1)/2;
int dct[N*5],tot=0;
struct Info 
{
	int x,l,r,v;
}seq[N*5];
bool cmp(Info A,Info B)
{
	return A.x<B.x;
}
int cnt=0;
int get(int x)
{
	return lower_bound(dct+1,dct+tot+1,x)-dct; 
}
int siz[N];
int calc(int x)
{
	if(A[x].empty())return dp[x][2];
	tot=0;
	dct[++tot]=st[x];
	dct[++tot]=ed[x]+1;
	for(int i:A[x])
	{
		int u=U[i],v=V[i];
		dct[++tot]=st[u];dct[++tot]=ed[u]+1;
		dct[++tot]=st[v];dct[++tot]=ed[v]+1;
	}
	sort(dct+1,dct+tot+1);
	tot=unique(dct+1,dct+tot+1)-dct-1;
	for(int i=1;i<=tot;i++)dis[i]=T.query(1,1,n,dct[i],dct[i+1]-1);
	S.build(1,1,tot);
	cnt=0;
	seq[++cnt]=(Info){st[x],st[x],ed[x]+1,1};
	seq[++cnt]=(Info){ed[x]+1,st[x],ed[x]+1,1};
	for(int i:A[x])
	{
		int u=U[i],v=V[i];
		seq[++cnt]=(Info){st[u],st[v],ed[v]+1,2};
		seq[++cnt]=(Info){ed[u]+1,st[v],ed[v]+1,inv2};
		seq[++cnt]=(Info){st[v],st[u],ed[u]+1,2};
		seq[++cnt]=(Info){ed[v]+1,st[u],ed[u]+1,inv2};
	}
	sort(seq+1,seq+cnt+1,cmp);
	int res=0;
	for(int i=1;i<=cnt;i++)
	{
		if(i>1)res=(res+1ll*T.query(1,1,n,seq[i-1].x,seq[i].x-1)*S.sum[1]%mod)%mod;
		S.mul(1,1,tot,get(seq[i].l),get(seq[i].r)-1,seq[i].v);
	}
	for(int i=flink[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==jump[x][0])continue;
		int V=T.query(1,1,n,st[y],ed[y]); 
		res=(res-1ll*V*V%mod+mod)%mod;
	}
	res=1ll*res*inv2%mod*ipw[tree[x]]%mod;
	return res;
}
void dfs3(int x,int pre)
{
	fup[x]+=siz[x]-Down[x].size();
	for(int i=flink[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		fup[y]=fup[x]+tree[x]-fdown[y];
		dfs3(y,x);
	}
	for(auto u:Down[x])T.mul(1,1,n,st[u],ed[u],2);
	dp[x][0]=1;
	for(int i=flink[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		for(int c=0;c<=3;c++)f[c]=dp[x][c],dp[x][c]=0;
		for(int c=0;c<=3;c++)
		{
			dp[x][c]=plu(dp[x][c],1ll*f[c]*pw[fdown[y]]%mod);
			dp[x][min(3,c+1)]=plu(dp[x][min(3,c+1)],1ll*f[c]*T.query(1,1,n,st[y],ed[y])%mod);
		}
	}
	for(int i=flink[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		T.mul(1,1,n,st[y],ed[y],pw[tree[x]-fdown[y]]);
	}
	int F=0;
	if(key[x])
	{
		for(int c=0;c<=3;c++)
		F=(F+mod-dp[x][c])%mod; 
	}
	F=(F+dp[x][3])%mod;
	ans=(ans+1ll*(F+calc(x))%mod*pw[fup[x]]%mod)%mod;
	F=(F+dp[x][2])%mod;
	T.upd(1,1,n,st[x],F);
}
int main()
{
	int tp;
	cin>>tp;
	cin>>n>>m>>K;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		if(st[x]>st[y])swap(x,y);
		if(Anc(x,y))
		{	
			Up[y].push_back(x);
			Down[x].push_back(y);
			fdown[Jump(y,x)]++;
		}
		else A[lca(x,y)].push_back(i);
		siz[x]++;siz[y]++;
		U[i]=x;V[i]=y;
	}
	for(int i=1;i<=K;i++)
	{
		int x;
		scanf("%d",&x);
		key[x]=1;
	}
	pw[0]=1;ipw[0]=1;
	for(int i=1;i<=m;i++)
	{
		pw[i]=1ll*pw[i-1]*2%mod;
		ipw[i]=1ll*ipw[i-1]*inv2%mod;
	}
	dfs2(1,0);
	T.build(1,1,n);
	dfs3(1,0);
	cout<<(mod-ans)%mod;
	return 0;
}

标签:return,int,res,jump,dep,NOI2023,mod
From: https://www.cnblogs.com/jesoyizexry/p/17594416.html

相关文章

  • [NOI2023] 字符串
    对于给出的串\(S\),将其拓展成\(S+\)特殊字符\(+rev(S)\),求出其后缀数组。那么对于一个子串\([l,r]\),合法的必要条件是\(l\)的后缀在后缀数组的排名小于\(r\)的前缀的排名。之所以是必要条件,是因为会记入一些\([l,r]\)是回文串且\(l\)的排名小的情况。具体而言,这......
  • P9482 [NOI2023] 字符串
    P9482[NOI2023]字符串限制长的很像回文串,但是是字典序关系。定睛一看比较的是原串\(s\)的一个后缀的前缀和翻转串\(s'\)的一个后缀的前缀比字典序。直接把\(s'\)拼到\(s\)后面,中间加个分隔符,来一次后缀排序。排名小的后缀字典序比排名大的后缀小。设当前比较的是......
  • 2023 联合省选-PKUSC2023-NOI2023游记
    在这段时间主要在学文化课,没怎么停课,天天暴力拼盘,所以索性合在一起。感觉非常意识流,和OI关系好像也不大。pig嫌我开始写的太短,我积极听取他人建议,加了一车流水账。联赛结束以后就退役了。因为即使NGOI也大概率会被卡“省线”,但还打算参加省选碰碰运气。遂在省选前两周申请一周半......
  • NOI2023游寄
    Before提前若干天到成都,感觉环境很好啊。提前参观成七,果然是别人的学校,有\(NOI\)那味了打了套全真模拟,但是没出结果,不重要,反正啥也不会。、在宾馆/成七打了一堆板子,适应了键盘,其实用起来还不错?最后一天晚上出去吃,和\(Kaguya\)和牛老师吃了一顿麻辣烫,体验良好,出了很多汗......
  • NOI2023 游记
    Day???来nfls集训并见证了一半的HN省队都在南京的奇景。认真打了一个月模拟赛,感觉还不错,终于有一套比较稳定的策略了虽然不时过不了大众题,在第14场的时候因为见过原题首次冲进前十,太感动了!因为补觉错过了UNR,保住了一点信心。最后一周的时候感觉有点累,润回长沙开摆了,算......
  • NOI2023 退役记
    Day-4打UNR,寄。具体情况见UNR游记。Day-3做了近九小时的车,来到了成都。众所周知,我是擅长睡觉的。所以,像是往常坐车的话,基本上都有一半的时间都睡过去了。然而这次,虽然路上很困,但是竟然全程没有睡着。大抵就是,感觉哪里不是很舒服就是了,有点累。想要睡着但是完全睡不......
  • NOI2023 又寄
    来成都之前,我一直认为自己拥有金牌的实力,也无论如何都有前\(100\)保底。而现实呢?\(100+95+60+52+100+44+10=461\),放到正式选手中是\(\texttt{rk120}\),如此拉跨的成绩。就算把所有会的分写上,且不挂分,也只有\(100+95+70+68+100+44+30=507\),仍旧没有金牌。\(\texttt{Day2}\)......
  • 洛谷 P9479 - [NOI2023] 桂花树
    显然,条件一等价于在\(T'\)中,\(1\simn\)组成的虚树等于它本身。条件二等价于\(1\simi\)组成的虚树上点的标号不超过\(i+k\)。我们考虑在原树的基础上依次添加\(n+1\simn+m\)这\(m\)个点。添加一个点\(i\)时,它与原树的位置关系可能有以下几种:挂在原树上某......
  • NOI2023游记
    DAY-1到达NOI赛场成都七中!太美丽了成七哎呦,这不考场吗乐!来成七报道,各种拍照领资料,折腾半天才到寝室。宿舍没有电梯(拎箱子累死我了),差评空调吹完还是好热,差评床好小虽然只是正常寝室床大小,差评晚上折腾半天终于睡着了DAY0这一天我们开始了万众瞩目的开幕式,然而年轻的......
  • NOI2023游记
    凡事有最后一次,就会有第一次。这个赛季,我第一次以正式选手参加NOIP,第一次参加联合省选,第一次进入浙江省队,第一次参加NOI。第一次和别人交换徽章,尽管认识的人不多;第一次Day2翻盘,尽管翻得不是很彻底;第一次拿到了真正意义上的牌子,尽管心有不甘。谁也不知道这第一次是否会是最后......