题解 P3242 【[HNOI2015]接水果】

· · 题解

从下午三点开此题调到到七点，A 掉此题的感觉真的是太爽了！！！

而且我觉得这道题对于练整体二分非常的好，就是写的人有点少。

不过为什么盘子是水果的子路径才是接住啊。。。不应该盘子比水果大的嘛。。。

我们将此路径覆盖分两类讨论：

不妨令 st_x<st_y

1、LCA(x,y)=x

那么我们发现其实路径一个端点在 [st_y,ed_y]，另一个不在除 x,y 外 x->y 的路径上的点 z 的子树内就行了，即 [1,st_z-1]\ or\ [ed_z+1,n]。其实用树剖一直向上跳，跳到离 x 最近的点且其子树内包含 y 就是 z 了。

2、LCA(x,y)\not =x

那么一个点在 [st_x,ed_x]，另一个点在 [st_y,ed_y] 就行了

发现可以做一遍扫描线，直接暴力树套树。在内层线段树动态开点，然后二分答案，\log^2 n 验证，时间复杂度 O(n\log^3n)，空间复杂度 O(n\log^2 n)

那有没有更好的解法呢？发现没有离线，第 k 小，

我们可以请出我们的整体二分！

然后正解就是扫描线+整体二分了。把矩形差分一下，然后区间加，单点查，套一个差分的树状数组就好了。时间复杂度 O(n\log^2 n)，空间复杂度 O(n)

Code\ Below: 
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=40000+10;
int n,m,Q,c[maxn],ans[maxn],mp[maxn],lim,head[maxn],to[maxn<<1],nxt[maxn<<1],tot,cnt;
int top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn],st[maxn],ed[maxn],tim;

struct Query{
    int op,x,l,r,k,v,id;
}q[maxn*5],q1[maxn*5],q2[maxn*5];

bool cmp(Query a,Query b){
    if(a.x!=b.x) return a.x<b.x;
    return a.op<b.op;
}

inline void read(int &x){
    x=0;int f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    if(f==-1) x=-x;
}
void print(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

inline void upd(int x,int y){
    for(;x<=n;x+=lowbit(x)) c[x]+=y;
}
inline int sum(int x){
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

inline void add(int x,int y){
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

void dfs1(int x,int f){
    fa[x]=f;siz[x]=1;
    dep[x]=dep[f]+1;
    int maxson=-1;
    for(int i=head[x],y;i;i=nxt[i]){
        y=to[i];
        if(y==f) continue;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>maxson){
            maxson=siz[y];
            son[x]=y;
        }
    }
}

void dfs2(int x,int topf){
    top[x]=topf;
    st[x]=++tim;
    if(son[x]) dfs2(son[x],topf);
    for(int i=head[x],y;i;i=nxt[i]){
        y=to[i];
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
    ed[x]=tim;
}

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}

int getson(int x,int y){
    while(top[x]!=top[y]){
        if(fa[top[x]]==y) return top[x];
        x=fa[top[x]];
    }
    return son[y];
}

void solve(int L,int R,int l,int r){
    if(L>R) return ;
    if(l==r){
        for(int i=L;i<=R;i++)
            if(q[i].op==2) ans[q[i].id]=mp[l];
        return ;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0,val;
    for(int i=L;i<=R;i++){
        if(q[i].op==1){
            if(q[i].k<=mid){
                upd(q[i].l,q[i].v);upd(q[i].r+1,-q[i].v);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        else {
            val=sum(q[i].l);
            if(val>=q[i].k) q1[++cnt1]=q[i];
            else q[i].k-=val,q2[++cnt2]=q[i];
        }
    }
    for(int i=1;i<=cnt1;i++) q[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[L+i+cnt1-1]=q2[i];
    solve(L,L+cnt1-1,l,mid);solve(L+cnt1,R,mid+1,r);
}

int main()
{
    read(n),read(m),read(Q);
    int x,y,z,l,r,k,lca;
    for(int i=1;i<n;i++){
        read(x),read(y);
        add(x,y);add(y,x);
    }
    dfs1(1,0);dfs2(1,1);
    for(int i=1;i<=m;i++){
        read(x),read(y),read(k);mp[i]=k;
        if(st[x]>st[y]) swap(x,y);
        lca=LCA(x,y);
        if(lca==x){
            z=getson(y,x);
            if(st[z]>1){
                q[++cnt]=(Query){1,1,st[y],ed[y],k,1,0};
                q[++cnt]=(Query){1,st[z],st[y],ed[y],k,-1,0};
            }
            if(ed[z]<n){
                q[++cnt]=(Query){1,st[y],ed[z]+1,n,k,1,0};
                q[++cnt]=(Query){1,ed[y]+1,ed[z]+1,n,k,-1,0};
            }
        }
        else {
            q[++cnt]=(Query){1,st[x],st[y],ed[y],k,1,0};
            q[++cnt]=(Query){1,ed[x]+1,st[y],ed[y],k,-1,0};
        }
    }
    sort(mp+1,mp+m+1);
    lim=unique(mp+1,mp+m+1)-mp-1;
    for(int i=1;i<=cnt;i++) q[i].k=lower_bound(mp+1,mp+lim+1,q[i].k)-mp;
    for(int i=1;i<=Q;i++){
        read(x),read(y),read(k);
        if(st[x]>st[y]) swap(x,y);
        q[++cnt]=(Query){2,st[x],st[y],0,k,0,i};
    }
    sort(q+1,q+cnt+1,cmp);
    solve(1,cnt,1,lim);
    for(int i=1;i<=Q;i++) printf("%d\n",ans[i]);
    return 0;
}