Barbecue【省选模拟赛】

分治后利用单调性two-pointers


本文总阅读量
Posted by yjjr's blog on April 13, 2018

标签:分治,two-pointers

题目

问题描述

Lyra 去野外旅游,准备试验刚买的烧烤架,于是她⾛到了附近的⼀棵树下想把树的⼀部分砍下来作为燃料。

树可以看成⼀棵 n 个点编号为 1 ∼ n 的⽆向⽆环图,Lyra 要求她砍下来的部分必须是⼀个连通块,编号也必须连续,她想知道她有多少种不同的砍法。

即给定⼀棵树,问多少个不同的区间 [L, R] 满⾜编号为 [L, R] 的点在树上组成⼀个连通块。

分析

考虑每个点对答案的贡献

先以这个点为根做一遍dfs,预处理出每个点到根的路径上的最值

这样做肯定会TLE,我们需要用分治来降低复杂度

考虑一个区间[l,r],我们每次以mid为根来进行dfs

发现一个区间内满足条件的最值都是单调不降的,然后用two-pointers解决

把时间复杂度优化到\(O(n\log n)\)

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define ll long long
#define reg(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
#define mid ((l+r)>>1)
const int maxn=3e5+6;
int T,n,cnt,last[maxn],fa[maxn],fl[maxn],fr[maxn],num[maxn];
struct edge{int to,next;}e[maxn<<2];
void insert(int u,int v){
	e[++cnt]=(edge){v,last[u]};last[u]=cnt;
	e[++cnt]=(edge){u,last[v]};last[v]=cnt;
}
void dfs(int l,int r,int x,int mnp,int mxp){
	mnp=min(mnp,x),mxp=max(mxp,x);
	fl[x]=mnp,fr[x]=mxp;
	reg(i,x){
		if(e[i].to==fa[x])continue;
		if(e[i].to>=l&&e[i].to<=r){fa[e[i].to]=x;dfs(l,r,e[i].to,mnp,mxp);}
	}
}//dfs处理出以mid为根的路径上的点的最值
inline ll solve(int l,int r){
	if(l>r)return 0;if(l==r)return 1;
	ll re=0;int jl,jr,fm;
	rep(i,l,r){fl[i]=n+1;fr[i]=-1;}
	fa[mid]=0;dfs(l,r,mid,mid,mid);num[mid-1]=1;fm=mid;
	rep(i,mid,r){fm=max(fm,fr[i]);num[i]=(fm<=i)?num[i-1]+1:num[i-1];}
	jl=jr=fm=mid;
	for(int i=mid;i>=l&&(~fr[i]);i--){
		fm=min(fm,fl[i]);jl=max(jl,fr[i]);
		while(jr<=r&&fl[jr]>=i&&(~fr[jr]))jr++;
		if(fm>=i&&jl<jr)re+=num[jr-1]-num[jl-1];
	}//two-pointers单调不降求解
	re+=solve(l,mid-1)+solve(mid+1,r);
	return re;
}
int main(){
	T=read();
	while(T--){
		n=read();
		mem(last,0);cnt=0;
		rep(i,1,n-1){
			int u=read(),v=read();
			insert(u,v);
		}
		printf("%lld\n",solve(1,n));
	}
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr