【题解】[HNOI2015] 接水果 整体二分 LuoguP3242 —Qiuly

怎么这么长……

原来是我板子有点长（

见到第 $k$ 大并且离线就可以想到整体二分吧？很裸。

然后会发现唯一的难点在于如何处理路径相交。

考虑对于路径 $u\rightarrow v$ ：

• $lca(u,v)$ 既不等于 $u$ 也不等于 $v$ ，如果 $u\rightarrow v$ 被 $a\rightarrow b$ 覆盖，那么 $a,b$ 分别在 $u,v$ 的子树中。

• $lca(u,v)$ 等于 $u$ 或 $v$ ，假如等于 $u$ ，如果 $u\rightarrow v$ 被 $a\rightarrow b$ 覆盖，那么 $a,b$ 一个在 $v$ 子树内，一个在 $u$ 的上子树内。

知道了取值区间就可以想成一个矩阵 (对于第二种情况其实是两个矩阵)，然后判断一个点属于多少矩阵，即一个点被多少矩阵覆盖。

这里的话不用二维 $\rm{BIT}$ 将矩阵拆成多个，按照 $x$ 排序处理即可。

int c1=0,c2=0,tot=0,mid=(val_l+val_r)>>1;
for(int i=val_l;i<=mid;++i) {
    int u=p[i].u,v=p[i].v,_lca=lca(u,v);
    if(_lca==v) {
        v=get_son(u,v);
        tmp[++tot]=(Data){dfn[u],1,dfn[v],1,0},
        tmp[++tot]=(Data){out[u],1,dfn[v],-1,0},
        tmp[++tot]=(Data){out[v],dfn[u],out[u],1,0},
        tmp[++tot]=(Data){n+1,dfn[u],out[u],-1,0};
    } else {
        tmp[++tot]=(Data){dfn[u],dfn[v],out[v],1,0},
        tmp[++tot]=(Data){out[u],dfn[v],out[v],-1,0};
    }
}
for(int i=l;i<=r;++i) tmp[++tot]=(Data){dfn[f[i].u],dfn[f[i].v],0,0,i};

sort(tmp+1,tmp+1+tot);
for(int i=1;i<=tot;++i) {
    if(!tmp[i].id&&tmp[i].l<=tmp[i].r) {
        if(tmp[i].l<=n) bit.update(tmp[i].l,tmp[i].val);
        if(tmp[i].r<=n) bit.update(tmp[i].r,-tmp[i].val);
    } else {
        int res=bit.query(tmp[i].l);
        if(f[tmp[i].id].k<=res) f1[++c1]=f[tmp[i].id];
        else f[tmp[i].id].k-=res,f2[++c2]=f[tmp[i].id];
    }
}

另外矩阵和点一定要注意，一定要确定好 $x,y$ 的坐标大小关系。

如果懒得判你也可以多加几个询问（

int main() {
    IN(n),IN(m),IN(q);
    for(int i=2;i<=n;++i) addedge();
    dfs(1,0);

    for(int i=1;i<=m;++i) {
        IN(p[i].u),IN(p[i].v),IN(p[i].c);
        if(dfn[p[i].u]<dfn[p[i].v]) swap(p[i].u,p[i].v);
    }
    for(int i=1;i<=q;++i) {
        IN(f[i].u),IN(f[i].v),IN(f[i].k),f[i].id=i;
        if(dfn[f[i].u]<dfn[f[i].v]) swap(f[i].u,f[i].v);
    }

    sort(p+1,p+1+m,cmp_p);
    solve(1,q,1,m);
    for(int i=1;i<=q;++i) _print(ans[i]);
    return 0;
}