题解：P3242 [HNOI2015] 接水果

kkxacj · 2025-06-30 17:24:40 · 题解

提供一个 O\left(n\log^2n\right) 的树套树做法。

思路

我们先随便假设一个根跑一遍树，然后稍微画一下图就会发现，我们需要把盘子分为两类，我们下文默认 dep_u \le dep_v,dep_x \le dep_y。

第一类是 u \ne \operatorname{lca}\left(u,v\right)，那么它能接到的水果必须满足 x 是 u 子树内的点，y 是 v 子树内的点，这样一定能完美包含。

否则就是 u = \operatorname{lca}\left(u,v\right)，这时我们会发现，只要两个点分别在两侧即可，即下图：

我们记 z 表示 u 到 v 第一个点，那么绿色部分就是除了 z 子树内的点。

我们容易想到树转序列，考虑求出 dfs 序，然后上面两个就可以理解为以下两个式子。

为了方便展示，记 L_i = dfn_i,R_i = dfn_i+siz_i-1。

第一种是 L_u \le L_x \le R_u,L_v \le L_y \le R_v。

第二种是 1 \le L_x < L_z,L_v \le L_y \le R_v 和 L_v \le L_x \le R_v,R_z < L_y \le n。

注意到第二类有转换，这是因为我们默认了 L_x \le L_y，所以需要交换每个所被包含的区间，第二类是没交集的，所以可以转化为第一类。

然后对于一次操作可以在 l 处加入，r+1 处删除，离线询问便可以解决第一维。

对于第二维，直接区间加即可，我们考虑树套树，每个节点开一个可持久化线段树，因为只会单点查，所以考虑标记永久化，每次往 \log 个区间加入一个值即可。

查询时把经过的 root_p 都记录下来，然后考虑线段树上二分，每次就给每个的都求一下判即可，root_p 最多 \log 个，离散化之后复杂度和空间都是 O\left(n\log^2n\right) 的，跑的还是挺快的，单点最大也就两百毫秒左右。

code

#include<bits/stdc++.h>
using namespace std;
#define mid ((L+R)>>1)
#define ls (p<<1)
#define rs ((p<<1)+1)
#define getchar() (p1 == p2 && (p2 = (p1 = buf1) + fread(buf1, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf1[1 << 23], *p1 = buf1, *p2 = buf1, ubuf[1 << 23], *u = ubuf;
namespace IO
{
    template<typename T>
    void read(T &_x){_x=0;int _f=1;char ch=getchar();while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();_x*=_f;}
    template<typename T,typename... Args>
    void read(T &_x,Args&...others){Read(_x);Read(others...);}
    const int BUF=20000000;char buf[BUF],to,stk[32];int plen;
    #define pc(x) buf[plen++]=x
    #define flush(); fwrite(buf,1,plen,stdout),plen=0;
    template<typename T>inline void print(T x){if(!x){pc(48);return;}if(x<0) x=-x,pc('-');for(;x;x/=10) stk[++to]=48+x%10;while(to) pc(stk[to--]);}
}
using namespace IO;
const int N = 4e4+10;
int n,p,q,head[N],cnt,x,y,z,lca,Z,ans[N],l,r;
int a[N],siz[N],son[N],dep[N],fa[N],col[N],dfn[N],ed[N],id[N],cnt1;//经典树剖 
int T[N],cnt2;//离散化
int cnt3,root[N<<2],Id;
int E[N],tot;//log个点给提出来 
struct w3
{
    int l,L,R,z,k;
}P[N<<3];
struct w2
{
    int x,y,z,id;
}Q[N];
struct w
{
    int to,nxt;
}b[N<<1];
struct w1
{
    int l,r,dat;
}c[N*250];
inline void add(int x,int y)
{
    b[++cnt].nxt = head[x];
    b[cnt].to = y;
    head[x] = cnt;
} 
void dfs(int x,int y)
{
    siz[x] = 1,dep[x] = dep[y]+1,fa[x] = y;
    for(int i = head[x];i;i = b[i].nxt)
        if(b[i].to != y)
        {
            dfs(b[i].to,x),siz[x] += siz[b[i].to];
            if(siz[b[i].to] > siz[son[x]]) son[x] = b[i].to;
        }
}
void dfs1(int x,int y,int z)
{
    col[x] = z,dfn[x] = ++cnt1,id[cnt1] = x;
    if(!son[x]) return;
    dfs1(son[x],x,z);
    for(int i = head[x];i;i = b[i].nxt)
        if(b[i].to != y && b[i].to != son[x])
            dfs1(b[i].to,x,b[i].to);
}//树剖 
inline int Lca(int x,int y)
{
    while(col[x] != col[y])
    {
        if(dep[col[x]] < dep[col[y]]) swap(x,y);
        x = fa[col[x]];
    }
    if(dfn[x] > dfn[y]) swap(x,y);
    return x;
}//求lca 
inline int Lca1(int x,int y)
{
    while(col[x] != col[y])
    {
        if(fa[col[y]] == x) return col[y];
        y = fa[col[y]];
    }
    return son[x];
}//x->y路径上第一个点(保证x是y的祖先) 
inline bool cmp3(w3 x,w3 y){ return x.l < y.l;}
inline bool cmp2(w2 x,w2 y){ return dfn[x.x] < dfn[y.x];}
void change(int &p,int L,int R,int l)
{
    if(!p) p = ++cnt;
    c[p].dat += Id;//Id看是加还是减 
    if(L == R) return;
    if(l <= mid) change(c[p].l,L,mid,l);
    else change(c[p].r,mid+1,R,l);
}
void Change(int p,int L,int R,int l,int r,int k)
{
    if(l <= L && R <= r)
    {
        change(root[p],1,cnt2,k);
        return;
    }
    if(l <= mid) Change(ls,L,mid,l,r,k);
    if(mid < r) Change(rs,mid+1,R,l,r,k);
}
void Query(int p,int L,int R,int l)
{
    E[++tot] = root[p];
    if(L == R) return;
    if(l <= mid) Query(ls,L,mid,l);
    else Query(rs,mid+1,R,l);
}
int query(int L,int R,int k)
{
    int sum = 0;
    if(L == R) return L; 
    for(int i = 1;i <= tot;i++) sum += c[c[E[i]].l].dat;
    if(sum >= k)
    {
        for(int i = 1;i <= tot;i++) E[i] = c[E[i]].l;
        return query(L,mid,k);
    }
    else
    {
        for(int i = 1;i <= tot;i++) E[i] = c[E[i]].r;
        return query(mid+1,R,k-sum);
    }
}
signed main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n),read(p),read(q);
    for(int i = 1;i < n;i++) read(x),read(y),add(x,y),add(y,x);
    dfs(1,0),dfs1(1,0,1);
    for(int i = 1;i <= n;i++) ed[i] = dfn[i]+siz[i]-1;
    for(int i = 1;i <= p;i++)
    {
        read(x),read(y),read(z),T[++cnt2] = z;
        if(dfn[x] > dfn[y]) swap(x,y);
        lca = Lca(x,y); 
        if(x != lca)
        {
            P[++cnt3].l = dfn[x],P[cnt3].L = dfn[y],P[cnt3].R = ed[y],P[cnt3].k = 1,P[cnt3].z = z;
            P[++cnt3].l = ed[x]+1,P[cnt3].L = dfn[y],P[cnt3].R = ed[y],P[cnt3].k = -1,P[cnt3].z = z;
        }
        else
        {
            Z = Lca1(x,y);
            P[++cnt3].l = 1,P[cnt3].L = dfn[y],P[cnt3].R = ed[y],P[cnt3].k = 1,P[cnt3].z = z;
            P[++cnt3].l = dfn[Z],P[cnt3].L = dfn[y],P[cnt3].R = ed[y],P[cnt3].k = -1,P[cnt3].z = z;
            P[++cnt3].l = dfn[y],P[cnt3].L = ed[Z]+1,P[cnt3].R = n,P[cnt3].k = 1,P[cnt3].z = z;
            P[++cnt3].l = ed[y]+1,P[cnt3].L = ed[Z]+1,P[cnt3].R = n,P[cnt3].k = -1,P[cnt3].z = z;
        }
    } cnt = 0;
    sort(T+1,T+1+cnt2); cnt2 = unique(T+1,T+1+cnt2)-T-1;
    for(int i = 1;i <= q;i++) 
    {
        read(Q[i].x),read(Q[i].y),read(Q[i].z),Q[i].id = i;
        if(dfn[Q[i].x] > dfn[Q[i].y]) swap(Q[i].x,Q[i].y);
    }
    sort(Q+1,Q+1+q,cmp2); sort(P+1,P+1+cnt3,cmp3); l = 1;
    for(int i = 1;i <= cnt3;i++) P[i].z = lower_bound(T+1,T+1+cnt2,P[i].z)-T;
    for(int i = 1;i <= q;i++)
    {
        if(dfn[Q[i].x] > dfn[Q[i].y]) swap(Q[i].x,Q[i].y);
        while(l <= cnt3 && P[l].l <= dfn[Q[i].x]) Id = P[l].k,Change(1,1,n,P[l].L,P[l].R,P[l].z),l++;
        tot = 0; Query(1,1,n,dfn[Q[i].y]);
        ans[Q[i].id] = query(1,cnt2,Q[i].z);
    }
    for(int i = 1;i <= q;i++) print(T[ans[i]]),pc('\n');
    flush();
    return 0;
}