Description

给定一棵树。
我们认为一条从 \(x\to y\) 的简单路径是好的，当且仅当路径上的点中编号最小的是 \(x\)，最大的是 \(y\)。
请求出好的简单路径条数。

Solution

先考虑序列上怎么做，可以考护两个单调栈，查询的时候 upper_bound 一下。但是一个更直接的做法是建出两棵笛卡尔树，一个大根一个小根，那么满足条件的点对在两棵树中一定互为祖父关系，那么把询问差分之后就是一个经典二维偏序问题。类比于序列上的问题，在树上一个类似笛卡尔树的结构是 Kruskal 重构树。与边的重构树不同，点的重构树不是二叉树，但是满足重构树上任意两点的 Lca 一定是原树上两点路径上的权值最小（最大）值的节点。树的构建可以考虑从小到大加点，遍历所有与当前点相连的且已经在重构树中的连通块，将该连通块的父亲指向当前点。之后的问题就和序列上一样了。

很卡常，不要用 vector，实测同样复杂度，邻接表满分，vector 75。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

typedef long long ll;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

const int N=2e6+7;

vector<int> g[N];

int c[N],n,m;
inline int lowbit(int x){return -x&x;}
inline void add(int x,int v){while(x<=n)c[x]+=v,x+=lowbit(x);}
inline int query(int x,int ret=0){
    while(x)ret+=c[x],x-=lowbit(x);return ret;
}

struct Tree{
    vector<int> e[N];
    int fa[N],Fa[N],in[N],out[N],timer=0;
    inline int find(int x){
        if(fa[x]==x) return x;
        return fa[x]=find(fa[x]);
    }
    void dfs(int u){
        in[u]=++timer;
        for(int v:e[u]) dfs(v);
        out[u]=timer;
    }
    void work(){
        for(int i=1;i<=n;i++)
            e[Fa[i]].push_back(i);
        dfs(find(1));
    }
}T1,T2;

struct Seg{
    int pos,l,r;
    bool operator <(const Seg &X) const{
        return pos<X.pos;
    }
}s[N];


struct Que{
    int pos,x,op;
    bool operator <(const Que &X) const{
        return pos<X.pos;
    }
}q[N*2];

int main(){
    freopen("charity.in","r",stdin);
    freopen("charity.out","w",stdout);
    n=read(); int x=read();
    for(int i=2;i<=n;i++){
        x=read();
        g[x].push_back(i);
        g[i].push_back(x);
    }
    for(int i=1;i<=n;i++)
        T1.fa[i]=T2.fa[i]=i;
    for(int i=1;i<=n;i++){
        for(int v:g[i]){
            if(v>i) continue;
            v=T1.find(v);
            T1.fa[v]=i,T1.Fa[v]=i;
        }
    }
    for(int i=n;i;i--){
        for(int v:g[i]){
            if(v<i) continue;
            v=T2.find(v);
            T2.fa[v]=i,T2.Fa[v]=i;
        }
    }
    T1.work(),T2.work();
    for(int i=1;i<=n;i++){
        q[++m]=(Que){T1.in[i],T2.in[i],-1};
        q[++m]=(Que){T1.out[i],T2.in[i],1};
        s[i]=(Seg){T1.in[i],T2.in[i],T2.out[i]};
    }
    sort(q+1,q+1+m),sort(s+1,s+1+n);
    ll ans=0;
    for(int i=1,hd=1;i<=m;i++){
        while(hd<=n&&s[hd].pos<=q[i].pos)
            add(s[hd].l,1),add(s[hd].r+1,-1),hd++;
        ans+=query(q[i].x)*q[i].op;
    }
    printf("%d",ans);
}