BZOJ3648：寝室管理

浅谈树分治：https://www.cnblogs.com/AKMer/p/10014803.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3648

基环树分治，结合了点分和边分的思想。

先随便拆掉环上一条边，我们先称它为基边，把它当做树做一遍，跟Free Tour II差不多。

剩下的问题就是如何统计经过基边的路径条数了。我们将基边连着的两个点分别成为\(st\)和\(ed\)，\(st\)的顺时针方向是\(ed\)，\(ed\)的逆时针方向是\(st\)。直接跟边分一样去分别处理\(st\)和\(ed\)能延伸出去的路径长度不行，因为这样会在环上产生交集然后统计不合法的路径。所以我们枚举基边以外的边去断开再统计答案，就可以保证统计出来的答案不重不漏了。

然后因为只要做一遍，所以大力树状数组也没关系。

时间复杂度：\(O(nlogn)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

#define low(i) ((i)&(-(i)))

const int maxn=1e5+5;

ll ans;

bool vis[maxn],bo;

int n,m,limit,tot=1,id,mx,rt,N;

int now[maxn],pre[maxn*2],son[maxn*2];

int siz[maxn],f[maxn],g[maxn],depest[maxn],V[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

void add(int a,int b) {

	pre[++tot]=now[a];

	now[a]=tot,son[tot]=b;

}

struct TreeArray {

	int c[maxn];

	void change(int pos,int v) {

		if(pos==n-13)mx++;

		for(int i=pos;i<=n;i+=low(i))

			c[i]+=v;

	}

	int query(int pos) {

		int res=0;

		for(int i=pos;i;i-=low(i))

			res+=c[i];

		return res;

	}

}T;

struct ring {

	int node1,node2;

	int dis[maxn],nxt[maxn],lst[maxn];

	bool find_ring(int fa,int u) {

		vis[u]=1;

		for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

			if(v!=fa) {

				if(vis[v])id=p>>1,node1=v,node2=u;

				if(vis[v]||find_ring(u,v)) {

					nxt[u]=v,lst[v]=u;

					return 1;

				}

			}

		return 0;

	}

	void dfs(int fa,int u,int num) {

		if(num==1)dis[u]=dis[fa]+1;

		T.change(n-dis[u]+1,num);

		for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

			if(!vis[v]&&v!=fa)dfs(u,v,num);

	}

	void query(int fa,int u) {

		dis[u]=dis[fa]+1,ans+=T.query(n-(max(1,limit-dis[u]))+1);

		for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

			if(!vis[v]&&v!=fa)query(u,v);

	}

	void work() {

		lst[node1]=node2;

		memset(vis,0,sizeof(vis));

		int st=son[id<<1],ed=son[id<<1|1];

		if(nxt[st]==ed)swap(st,ed);

		int pos=st;vis[ed]=1;

		while(pos!=ed)vis[pos]=1,pos=nxt[pos];

		dis[ed]=0,pos=st;mx=0;

		while(pos!=ed)dfs(lst[pos],pos,1),pos=nxt[pos];dfs(lst[ed],ed,1);

		pos=ed;dis[st]=0;

		while(pos!=st)dfs(nxt[pos],pos,-1),query(nxt[pos],pos),pos=lst[pos];

	}

}R;

void find_rt(int fa,int u) {

	int res=0;siz[u]=1;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(!vis[v]&&(p>>1)!=id&&v!=fa)

			find_rt(u,v),siz[u]+=siz[v],res=max(res,siz[v]);

	res=max(res,N-siz[u]);

	if(res<mx)mx=res,rt=u;

}

void dfs(int fa,int u,int dep) {

	mx=max(mx,dep),siz[u]=1;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(!vis[v]&&(p>>1)!=id&&v!=fa)

			dfs(u,v,dep+1),siz[u]+=siz[v];

}

bool cmp(int a,int b) {

	return depest[a]<depest[b];

}

void query(int fa,int u,int dep) {

	ans+=f[max(1,limit-dep)];

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(!vis[v]&&v!=fa&&(p>>1)!=id)query(u,v,dep+1);

}

void solve(int fa,int u,int dep) {

	g[dep]++;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(!vis[v]&&v!=fa&&(p>>1)!=id)solve(u,v,dep+1);

}

void work(int u,int size) {

	N=size,mx=rt=n+1,find_rt(0,u),u=rt,vis[u]=1,tot=0;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(!vis[v]&&(p>>1)!=id) {

			V[++tot]=v,mx=0;

			dfs(u,v,2),depest[v]=mx;

		}

	sort(V+1,V+tot+1,cmp);

	for(int i=1;i<=tot;i++) {

		query(u,V[i],1);

		solve(u,V[i],2);

		for(int j=depest[V[i]];j;j--)

			g[j]+=g[j+1],f[j]+=g[j];

		for(int j=1;j<=depest[V[i]];j++)g[j]=0;

	}

	ans+=f[limit];

	for(int i=1;i<=depest[V[tot]];i++)f[i]=g[i]=0;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(!vis[v]&&(p>>1)!=id)work(v,siz[v]);

}

int main() {

	n=read(),m=read(),limit=read();

	for(int i=1;i<=m;i++) {

		int a=read(),b=read();

		add(a,b),add(b,a);

	}

	if(m==n)R.find_ring(0,1);

	memset(vis,0,sizeof(vis));

    work(1,n);

	if(m==n)R.work();

	printf("%lld\n",ans);

	return 0;

}

巴特西

BZOJ3648：寝室管理

最新文章

热门文章