問題概要

ノード数が $ n $ の木が与えられ、各ノードには重み $ w_i $ が割り当てられている。$ q $ 個の操作を行う：

• 0 u v：ノード $ u $ の重みを $ v $ に変更する。
• k u v：ノード $ u $ から $ v $ へのパス上の重みの第 $ k $ 番目の大きい値を求める。パス上にノードが $ k $ 個未満ある場合、invalid request! を出力する。

制約

• $ 1 \le n, q \le 8 \cdot 10^4 $
• $ 1 \le k \le n $
• $ 1 \le w_i \le 10^8 $

実行時間制限は $ \texttt{2s} $、メモリ制限は $ \texttt{500MB} $。

解法の考察

木が線形に伸びた場合、区間内の第 $ k $ 番目小さい要素を求める問題は、主席木や全体二分法で解ける。この問題も同様に、これらの手法を修正して適用できる。

ツリー構造の木構造

主席木は更新に対応できないという欠点があるため、ツリー構造を用いて情報を保持する方法を検討する。

ノード $ u $ と $ v $ の最近共通祖先を $ p $ とすると、$ u \to v $ のパスは $ (u \to 1) + (v \to 1) - (p \to 1) - (fa_p \to 1) $ として表せる。各ノードから根までのパスの重み情報を保持すればよい。

更新操作は、元の木の部分木から重み $ w_i $ のノードを削除し、重み $ v $ のノードを追加することになる。

DFS順序上で区間操作を行うことになり、差分を用いて単点更新と前缀和の計算に変換できる。この処理はBIT + 重みセグメント木を用いて実現可能。

クエリではセグメント木を二分探索し、$ \mathcal{O}(\log n) $ 個の重みセグメント木のルートを同時に移動することで実現する。

離散化を忘れないように注意が必要で、さもないと $ \log $ 乗のメモリ使用量が許容できない。

時間計算量は $ \mathcal{O}((n+q)\log^2n) $。

#include<bits/stdc++.h>
using namespace std;
const int maxn=8e4+5;
int m,n,q,u,v,cnt,tot;
int d[maxn],fa[maxn][17];
int w[maxn],sz[maxn],dfn[maxn];
int c[2*maxn],rt[maxn];
vector<int> g[maxn];
struct oper
{
    int k,u,v;
}t[maxn];
struct node
{
    int ls,rs,sum;
}f[500*maxn];
void dfs(int u,int f)
{
    sz[u]=1,dfn[u]=++cnt;
    for(auto v:g[u])
    {
        if(v==f) continue;
        d[v]=d[u]+1,fa[v][0]=u;
        for(int i=1;i<=16;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
        dfs(v,u),sz[u]+=sz[v];
    }
}
int lca(int u,int v)
{
    if(d[u]<d[v]) swap(u,v);
    for(int i=16;i>=0;i--)
        if(d[fa[u][i]]>=d[v])
            u=fa[u][i];
    if(u==v) return u;
    for(int i=16;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
void pushup(int p)
{
    f[p].sum=f[f[p].ls].sum+f[f[p].rs].sum;
}
void modify(int &p,int l,int r,int pos,int val)
{
    if(!p) p=++tot;
    if(l==r) return f[p].sum+=val,void();
    int mid=(l+r)/2;
    if(pos<=mid) modify(f[p].ls,l,mid,pos,val);
    else modify(f[p].rs,mid+1,r,pos,val);
    pushup(p);
}
void add(int x,int v,int op)
{
    while(x<=n) modify(rt[x],1,m,v,op),x+=x&(-x);
}
void ask(int x,vector<int> &vec)
{
    while(x) vec.push_back(rt[x]),x-=x&(-x);
}
int query(int a,int b,int c,int d,int k)
{
    vector<int> v1,v2;
    ask(dfn[a],v1),ask(dfn[b],v1),ask(dfn[c],v2),ask(dfn[d],v2);
    int l=1,r=m;
    while(l!=r)
    {
        int cur=0,mid=(l+r)/2;
        for(auto &p:v1) cur+=f[f[p].ls].sum;
        for(auto &p:v2) cur-=f[f[p].ls].sum;
        if(cur>=k)
        {
            r=mid;
            for(auto &p:v1) p=f[p].ls;
            for(auto &p:v2) p=f[p].ls;
        }
        else
        {
            l=mid+1,k-=cur;
            for(auto &p:v1) p=f[p].rs;
            for(auto &p:v2) p=f[p].rs;
        }
    }
    return l;
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]),c[++m]=w[i];
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&u,&v);
        g[u].push_back(v),g[v].push_back(u);
    }
    d[1]=1,dfs(1,0);
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&t[i].k,&t[i].u,&t[i].v);
        if(!t[i].k) c[++m]=t[i].v;
    }
    sort(c+1,c+m+1);
    m=unique(c+1,c+m+1)-c-1;
    for(int i=1;i<=n;i++)
    {
        w[i]=lower_bound(c+1,c+m+1,w[i])-c;
        add(dfn[i],w[i],1),add(dfn[i]+sz[i],w[i],-1);
    }
    for(int i=1;i<=q;i++)
    {
        int k=t[i].k,u=t[i].u,v=t[i].v;
        if(!k)
        {
            add(dfn[u],w[u],-1),add(dfn[u]+sz[u],w[u],1);
            w[u]=lower_bound(c+1,c+m+1,v)-c;
            add(dfn[u],w[u],1),add(dfn[u]+sz[u],w[u],-1);
        }
        else
        {
            int p=lca(u,v),dis=d[u]+d[v]-2*d[p]+1;
            if(k>dis) printf("invalid request!\n");
            else printf("%d\n",c[query(u,v,p,fa[p][0],dis-k+1)]);
        }
    }
    return 0;
}

全体二分法

全体二分法は更新に対応できるため、コード量が少なくなる利点がある。

なぜ全体二分法は更新に対応できるのか？

全体二分法は値域の cdq 分治として理解できる。動的な区間第 $ k $ 小を例にすると：

• 更新とクエリが同じ側に存在する場合、再帰的に処理できる。
• 更新が $ mid $ 以下だがクエリが $ mid $ より大きい場合、$ \le mid $ の更新がクエリに与える影響を計算する必要がある。

時間軸上での依存関係があるが、全体二分法は操作を順番に処理するので時間軸の考慮は不要である。

二分した後、操作は「単点の増減」および「パスの総和」に変換される。

各ノードから根へのパスの結果を保持することで、単点の増減は部分木に影響を与える。

DFS順序により区間操作に変換し、差分BITで対応する。

時間計算量は $ \mathcal{O}((n+q)\log n\log V) $。

#include<bits/stdc++.h>
using namespace std;
const int maxn=8e4+5;
int k,m,n,q,u,v,cnt;
int d[maxn],fa[maxn][17];
int sz[maxn],dfn[maxn];
int c[maxn],w[maxn],res[maxn];
vector<int> g[maxn];
struct oper
{
    int k,p,u,v,id;
    ///id==0,k=1/-1 表示 u 番目のノードの重み v の貢献を追加/削除
    ///id!=0, u->v パスの第 k 小を求める, p は LCA, id は識別子
};
vector<oper> vec;
void dfs(int u,int f)
{
    sz[u]=1,dfn[u]=++cnt;
    for(auto v:g[u])
    {
        if(v==f) continue;
        d[v]=d[u]+1,fa[v][0]=u;
        for(int i=1;i<=16;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
        dfs(v,u),sz[u]+=sz[v];
    }
}
int lca(int u,int v)
{
    if(d[u]<d[v]) swap(u,v);
    for(int i=16;i>=0;i--)
        if(d[fa[u][i]]>=d[v])
            u=fa[u][i];
    if(u==v) return u;
    for(int i=16;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}
void add(int x,int v)
{
    while(x<=n) c[x]+=v,x+=x&(-x);
}
int ask(int x)
{
    int res=0;
    while(x) res+=c[x],x-=x&(-x);
    return res;
}
void solve(int l,int r,vector<oper> vec)
{
    if(vec.empty()) return ;
    if(l==r)
    {
        for(auto p:vec) res[p.id]=l;
        return ;
    }
    int mid=(l+r)/2;
    vector<oper> v1,v2;
    for(auto p:vec)
    {
        int &k=p.k,&u=p.u,&v=p.v;
        if(!p.id)
        {
            if(v<=mid) add(dfn[u],k),add(dfn[u]+sz[u],-k),v1.push_back(p);
            else v2.push_back(p);
        }
        else
        {
            int cur=ask(dfn[u])+ask(dfn[v])-ask(dfn[p.p])-ask(dfn[fa[p.p][0]]);
            if(cur>=k) v1.push_back(p);
            else k-=cur,v2.push_back(p);
        }
    }
    for(auto p:v1)
    {
        int k=p.k,u=p.u;
        if(!p.id) add(dfn[u],-k),add(dfn[u]+sz[u],k);
    }
    solve(l,mid,v1);
    solve(mid+1,r,v2);
}
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]),vec.push_back({1,0,i,w[i],0});
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&u,&v);
        g[u].push_back(v),g[v].push_back(u);
    }
    d[1]=1,dfs(1,0);
    while(q--)
    {
        scanf("%d%d%d",&k,&u,&v);
        if(!k) vec.push_back({-1,0,u,w[u],0}),w[u]=v,vec.push_back({1,0,u,w[u],0});
        else
        {
            int p=lca(u,v),dis=d[u]+d[v]-2*d[p]+1;
            if(k>dis) res[++m]=-1;
            else vec.push_back({dis-k+1,p,u,v,++m});
        }
    }
    solve(1,1e8,vec);
    for(int i=1;i<=m;i++)
        if(res[i]!=-1) printf("%d\n",res[i]);
        else printf("invalid request!\n");
    return 0;
}

木上の修正常態莫隊

この問題は木上の修正常態莫隊でも解ける。

欧拉順序により木のパスを「奇数回出現する要素」の区間として表現する。

集合を維持するために値域をブロック化する。

更新は $ \mathcal{O}(1) $、クエリでは一度走査して第 $ k $ 番目の要素が属するブロックを特定し、再度走査して具体的な値を求める。時間計算量は $ \mathcal{O}(\sqrt{n}) $。

時間軸を追加することで複数の更新に対応できる。

時間計算量は $ \mathcal{O}(n^{4/3}q^{1/3} + q\sqrt{n}) $。

#include
#define fi first
#define se second
#define mp make_pair
#define pii pair
using namespace std;
const int maxn=1.6e5+5,B=2000;
int l,m,n,q,r,t,u,v,cnt;
int d[maxn],fa[maxn][17];
int c[maxn],w[maxn],bel[maxn],res[maxn];
int id[maxn],st[maxn],ed[maxn];
pii h[maxn];
vector g[maxn];
struct oper
{
int k,u,v;
}f[maxn];
struct quer
{
int k,p,l,r,t,id;
};
vector vec;
void dfs(int u,int f)
{
st[u]=++cnt,id[cnt]=u;
for(auto v:g[u])
{
if(v==f) continue;
d[v]=d[u]+1,fa[v][0]=u;
for(int i=1;i<=16;i++) fa[v][i]=fa[fa[v][i-1]][i-1];
dfs(v,u);
}
ed[u]=++cnt,id[cnt]=u;
}
int lca(int u,int v)
{
if(d[u]=0;i--)
if(d[fa[u][i]]>=d[v])
u=fa[u][i];
if(u==v) return u;
for(int i=16;i>=0;i--)
if(fa[u][i]!=fa[v][i])
u=fa[u][i],v=fa[v][i];
return fa[u][0];
}
bool cmp(quer a,quer b)
{
if(bel[a.l]!=bel[b.l]) return bel[a.l]cnt[i]) k-=cnt[i];
else
{
for(int j=st[i];j<=ed[i];j++)
if(k>a[j]) k-=a[j];
else return j;
return assert(false),-1;
}
}
return assert(false),-1;
}
}
using block::add;
using block::work;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&u,&v);
g[u].push_back(v),g[v].push_back(u);
}
d[1]=1,dfs(1,0),cnt=0;
for(int i=1;i<=n;i++) c[++cnt]=w[i];
for(int i=1;i<=2*n;i++) bel[i]=(i-1)/B+1;
for(int i=1;i<=q;i++)
{
scanf("%d%d%d",&f[i].k,&f[i].u,&f[i].v);
if(!f[i].k) c[++cnt]=f[i].v;
}
sort(c+1,c+cnt+1);
cnt=unique(c+1,c+cnt+1)-c-1;
for(int i=1;i<=n;i++) w[i]=lower_bound(c+1,c+cnt+1,w[i])-c;
for(int i=1;i<=q;i++)
{
int k=f[i].k,u=f[i].u,v=f[i].v;
if(!k) h[++t]=mp(u,lower_bound(c+1,c+cnt+1,v)-c);
else
{
if(st[u]>st[v]) swap(u,v);
int p=lca(u,v),dis=d[u]+d[v]-2*d[p]+1;
m++;
if(k>dis) res[m]=-1;
else if(u==p) vec.push_back({dis-k+1,0,st[u],st[v],t,m});
else vec.push_back({dis-k+1,p,ed[u],st[v],t,m});
}
}
sort(vec.begin(),vec.end(),cmp);
l=1,r=0,t=0,block::init(cnt);
for(auto p:vec)
{
while(l>p.l) add(id[--l]);
while(rp.r) add(id[r--]);
while(tp.t) work(t--);
if(p.p) add(p.p);
res[p.id]=block::query(p.k);
if(p.p) add(p.p);
}
for(int i=1;i<=m;i++)
if(res[i]!=-1) printf("%d\n",c[res[i]]);
else printf("invalid request!\n");
return 0;
}