THUSC 2021 D1T2 及 CF490F 题解

Ranya · 2024-01-24 16:09:01 · 题解

前言：

发现题解区没有点分治（哭），树上路径问题不应该直接无脑大力点分治吗（哭哭）

这里提供一种 O(n\log^2 n) 的点分治，供思路相同的同学参考。

题意

给出一颗带点权树，求树上所有路径的严格上升子序列的最大值。

n\le 10^5 \quad a_i\le10^9

题解

正如前言所述，我们思考点分治在当前分治中心 u 如何计算答案。

一个显然的思路是记录 up_i,dn_i 分别表示从叶子往 u 走的所有路径中，以 i 结尾的严格递增/递减子序列的最长长度。

他们的求法可以通过离散化+记录时间戳 dfn 后线段树统计，对于 up，我们将点按照权值由小到大一次加入线段树，每次询问一个子树内的最大值，也就是线段树上单点加和区间查询。dn 则是由大到小。

然后将 up 做前缀 \max，dn 做后缀 \max，设 w 为 u 的点权，然后答案统计就可以分为：

子序列包含 u：up[w-1]+dn[w+1]+1
子序列不包含 u：\max {up[i]+dn[i+1]}

但聪明的你肯定会想到，要是两条路径分别来自同一棵子树，那不就寄了吗 QAQ

所以套路的，对 up,dn 记录最大值、最大值来自哪颗子树、次大值、次大值来自哪颗子树。然后答案统计的时候特判一下就好了。

常数在校内 OJ n=10^5 的情况下是常数最小的线段树合并的 4 倍。。

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
int read() {
    int x=0; char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48, ch=getchar();
    return x;
} 

const int N=1e5+3;
int n, ans, a[N], b[N], m, c[N];
vector<int> e[N];

int rt, all, mx[N], sz[N], vis[N];
int L[N], R[N], tim, bl[N];
int up1[N], gu1[N], up2[N], gu2[N], dn1[N], gd1[N], dn2[N], gd2[N];
vector<int> id[N];

void get_root(int u, int dad) {
    mx[u]=0, sz[u]=1;
    for (int v:e[u]) if (v!=dad&&!vis[v]) {
        get_root(v, u);
        mx[u]=max(mx[u], sz[v]);
        sz[u]+=sz[v];
    }
    mx[u]=max(mx[u], all-sz[u]);
    if (mx[u]<mx[rt]) rt=u;
}

void dfs(int u, int dad) {
    sz[u]=1;
    b[++m]=a[u];
    L[u]=++tim;
    for (int v:e[u]) if (v!=dad&&!vis[v]) {
        dfs(v, u);
        sz[u]+=sz[v];
    }
    R[u]=tim;
}
void dfs(int u, int dad, int o) {
    c[u]=lower_bound(b+1, b+1+m, a[u])-b;
    bl[u]=o;
    for (int v:e[u]) if (v!=dad&&!vis[v]) {
        dfs(v, u, o);
    }
    id[c[u]].push_back(u);
}

#define Rt 1, 1, all
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
#define Ls ls, l, mid
#define Rs rs, mid+1, r
int t[N<<2], lz[N<<2];
int ask(int i, int l, int r, int x, int y) {
    if ((x<=l&&r<=y)||!t[i]) return t[i];
    if (lz[i]) t[ls]=t[rs]=0, lz[ls]=lz[rs]=1, lz[i]=0;
    if (x>mid) return ask(Rs, x, y);
    if (y<=mid) return ask(Ls, x, y);
    return max(ask(Ls, x, y), ask(Rs, x, y));
}
void add(int i, int l, int r, int x, int v) {
    if (l==r) return t[i]=v, void();
    if (lz[i]) t[ls]=t[rs]=0, lz[ls]=lz[rs]=1, lz[i]=0;
    if (x<=mid) add(Ls, x, v);
    else add(Rs, x, v);
    t[i]=max(t[ls], t[rs]);
}
void New(int &fir, int &ff, int &sec, int &ss, int tmp, int o) {    
    if (tmp>fir) {
        if (ff!=o||ss==o) sec=fir, ss=ff;
        fir=tmp, ff=o;
    }
    else if (tmp>sec&&ff!=o) {
        sec=tmp, ss=o;
    }
}
void calc(int i, int &fir, int &ff, int &sec, int &ss) {
    fir=ff=sec=ss=0;
    queue<int> q;
    for (int u:id[i]) {
        int tmp=ask(Rt, L[u], R[u])+1;
        New(fir, ff, sec, ss, tmp, bl[u]);
        q.push(tmp);
    }
    for (int u:id[i]) add(Rt, L[u], q.front()), q.pop();
}
void split(int u) {
    m=tim=0;
    dfs(u, 0);
    sort(b+1, b+1+m);
    m=unique(b+1, b+1+m)-b-1;
    for (int v:e[u]) 
        if (!vis[v]) dfs(v, u, v);
    c[u]=lower_bound(b+1, b+1+m, a[u])-b;
    lz[1]=1, t[1]=0;
    for (int i=1; i<=m; i++) {
        calc(i, up1[i], gu1[i], up2[i], gu2[i]);
        New(up1[i], gu1[i], up2[i], gu2[i], up1[i-1], gu1[i-1]);
        New(up1[i], gu1[i], up2[i], gu2[i], up2[i-1], gu2[i-1]);
    }
    dn1[m+1]=gd1[m+1]=dn2[m+1]=gd2[m+1]=0;
    lz[1]=1, t[1]=0;
    for (int i=m; i>=1; i--) {
        calc(i, dn1[i], gd1[i], dn2[i], gd1[i]);
        New(dn1[i], gd1[i], dn2[i], gd2[i], dn1[i+1], gd1[i+1]);
        New(dn1[i], gd1[i], dn2[i], gd2[i], dn2[i+1], gd2[i+1]);
    }
    if (gu1[c[u]-1]!=gd1[c[u]+1]) ans=max(ans, up1[c[u]-1]+dn1[c[u]+1]+1);
    else {
        ans=max({ans, up1[c[u]-1]+dn2[c[u]+1]+1, up2[c[u]-1]+dn1[c[u]+1]+1});
    }
    for (int i=1; i<m; i++) {
        if (gu1[i]!=gd1[i+1]) ans=max(ans, up1[i]+dn1[i+1]);
        else {
            ans=max({ans, up1[i]+dn2[i+1], up2[i]+dn1[i+1]});
        }
    }
    for (int i=1; i<=m; i++) id[i].clear();
    vis[u]=1;
    for (int v:e[u]) if (!vis[v]) {
        rt=0, all=sz[v], get_root(v, u);
        split(rt);
    }
}

signed main() {
    n=read();
    for (int i=1; i<=n; i++) a[i]=read();
    for (int i=1; i<n; i++) {
        int u=read(), v=read();
        e[u].push_back(v), e[v].push_back(u);
    }
    mx[0]=n+1;
    rt=0, all=n, get_root(1, 0);
    split(rt);
    cout<<ans<<'\n';
    return 0;
}