标签：分治，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;
}
