Barbecue【省选模拟赛】

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