SPOJ COT - Count on a tree

SPOJ

Luogu

分析

看到第 $k$ 小可以考虑主席树,每个节点的主席树在父节点的版本上修改即可。

现在问题在于怎么求出一条链对应的主席树。可以考虑树上差分,即 $T_u+T_v-T_{lca}-T_{fa_{lca}}$ 。

那么求第 $k$ 小就是一个简单的主席树上二分了。

代码

这是 SPOJ 上的版本,要过洛谷 P2633 请自己加一个强制在线。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m,w[N],S[N],tp;

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

struct node { int ls,rs,sum; } t[N*30];
int rt[N],tot=0;
inline void modify(int& p,int q,int l,int r,int pos,int w) {
    t[p=++tot]=t[q];
    if (l==r) { t[p].sum+=w; return; }
    int mid=(l+r)>>1;
    if (pos<=mid) modify(t[p].ls,t[q].ls,l,mid,pos,w);
    else modify(t[p].rs,t[q].rs,mid+1,r,pos,w);
    t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum;
}
inline int query(int A,int B,int C,int D,int l,int r,int k) {
    if (l==r) return l;
    int mid=(l+r)>>1;
    int lsum=t[t[A].ls].sum+t[t[B].ls].sum-t[t[C].ls].sum-t[t[D].ls].sum;
    if (lsum>=k) return query(t[A].ls,t[B].ls,t[C].ls,t[D].ls,l,mid,k);
    else return query(t[A].rs,t[B].rs,t[C].rs,t[D].rs,mid+1,r,k-lsum);
}

int dep[N],fa[N],sz[N],hson[N],top[N];
inline void dfs1(int u,int f) {
    modify(rt[u],rt[f],1,tp,w[u],1);
    dep[u]=dep[fa[u]=f]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs1(v,u),sz[u]+=sz[v];
        if (sz[v]>sz[hson[u]]) hson[u]=v;
    }
}
inline void dfs2(int u,int anc) {
    top[u]=anc;
    if (hson[u]) dfs2(hson[u],anc);
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}

inline int getlca(int u,int v) {
    while (top[u]!=top[v]) {
        if (dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if (dep[u]<dep[v]) swap(u,v);
    return v;
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) S[i]=w[i]=read();
    sort(S+1,S+n+1),tp=unique(S+1,S+n+1)-S-1;
    for (re int i=1;i<=n;++i) w[i]=lower_bound(S+1,S+tp+1,w[i])-S;
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs1(1,0),dfs2(1,1);
    while (m--) {
        int u=read(),v=read(),k=read(),t=getlca(u,v);
        printf("%d\n",S[query(rt[u],rt[v],rt[t],rt[fa[t]],1,tp,k)]);
    }
    return 0;
}
最后修改:2019 年 10 月 04 日 08 : 10 AM

发表评论