跳到主要内容

山城巷图

· 阅读需 7 分钟

题解​

题意​

给定一棵包含 n 个节点的树，节点编号为 1 到 n，根为节点 1。每条边有一个整数高差 d，表示从父节点走向子节点时高度的增加量。

节点 1 的高度为 0；其余节点的高度为从根到该节点路径上所有边的高差之和。高差可以为负数或 0，不同节点的高度可以相同。

有 q 次独立询问，每次询问给定整数区间 l, r。对于所有满足 l ≤ x, y ≤ r 的节点对 (x, y)，标记它们的最近公共祖先 LCA(x, y)。允许 x = y，此时最近公共祖先为 x 本身。被标记的节点可以不在编号区间 l 到 r 内，同一节点被多次标记只计一次。

对每次询问，求所有被标记节点的高度共有多少种不同的取值。

数据范围

  • 1 ≤ n ≤ 10⁵
  • 1 ≤ q ≤ 5 × 10⁵
  • 1 ≤ u, v ≤ n，且 u ≠ v
  • -10⁹ ≤ d ≤ 10⁹
  • 1 ≤ l ≤ r ≤ n
  • 输入保证是一棵树

解法​

又是一个看起来十分不可做的题。

但是我们要逐个拆解这道题的含义。

每个点有一个权值，就是这个点到根节点的路径上的边权。

我们需要查询一个区间标记所有点对的LCALCA以及这些点本身，求出这些节点中不同权值的数量。

很容易想到我们可以考虑离线，我们把所有询问按照右端点排序，然后我们从左往右依次枚举每个点，每当我们加入一个新点的时候，考虑这个点可能会产生那些权值，我们发现只有可能是这个点到根路径上的每个点的权值，然后我们更新有那些编号小于这个点的点会与当前枚举的点形成贡献这个权值，产生相同权值的点对中我们取较小的编号的点编号最大的。然后我们对于每一个询问，我们只需要知道产生贡献点对中编号较小的点的编号大于LL的有多少，可以用一个树状数组维护。

然后我们发现我们的瓶颈在于，对于每个点，我们要怎么知道有哪些其他编号较小的点，会产生哪些贡献？

我们考虑每个点作为贡献，只有可能是被哪些点对作为LCALCA。

首先，这些点对中两个点一定属于不同的子树。

其次，我们发现，由于我们询问的是一个编号连续的区间，所以说假设一个编号为(1,3)(1,3)的点对会贡献某个节点的权值，另一个编号为(1,5)(1,5)的点对同样会贡献这个权值，那么这个(1,5)(1,5)的点对是多余的，因为一旦一个区间包含了[1,5][1,5]那么他一定也包含了[1,3][1,3]这个区间。

所以真正会产生贡献的点对只有来自不同子树，编号相邻的点对。

形式化的说,假设当前我们枚举到的节点为pp，它的子树中所有节点按照编号排序形成一个序列SS。

那么构成产生贡献deppdep_p的点对只有(x,lstx),(x,nxtx)(x,lst_x),(x,nxt_x)

其中x∈Sx \in S。

lstxlst_x 为序列中最后一个编号小于xx的不同子树的节点的编号，nxtxnxt_x为序列中第一个编号大于xx的不同子树的节点的编号。

由于每个点对中至少有一个节点属于轻儿子，而每个轻儿子只会贡献O(1)O(1)个点对，根据启发式合并的思想，每个点只会被作为O(log⁡n)O(\log n)次轻儿子，所以总点对的个数是O(log⁡n)O(\log n)的。

我们对于每个节点维护一个setset，然后继承重儿子的setset，枚举每个轻儿子，查询它们setset中的节点在父亲节点维护的setset中的前驱和后继，产生贡献的点对。这样我们就可以记录这个点对中编号较大的那个点，会和编号较小的点产生的贡献。然后我们再把这个轻儿子的setset与父亲节点维护的setset合并。

最后我们用刚开始说的做法就可以得到答案了

时间复杂度为O(nlog⁡2n)O(n \log^2 n)

代码​

code
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e5+10;
int n,m;
int head[N],ver[2*N],nxt[2*N],tot;
ll edge[2*N];
inline void add(int x,int y,ll z)
{
    ver[++tot]=y;
    edge[tot]=z;
    nxt[tot]=head[x];
    head[x]=tot;
    return ;
}
int tott;
struct node{
    int opt;
    int l,r;
    ll d;
    bool operator<(const node &b) const
    {
        if(r==b.r) return opt<b.opt;
        return r<b.r;
    }
} q[40*N];
ll dep[N],siz[N],son[N];
set<int> s[N];
inline void dfs(int x,int fa)
{
    siz[x]=1;
    ll maxx=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        ll z=edge[i];
        if(y==fa) continue;
        dep[y]=dep[x]+z;
        dfs(y,x);
        siz[x]+=siz[y];
        if(maxx<siz[y]) 
        {
            maxx=siz[y];
            son[x]=y;
        }
    }
    if(son[x]) swap(s[x],s[son[x]]);
    auto it=s[x].begin();
    if(s[x].size())
    {
        it=s[x].lower_bound(x);
        if(it!=s[x].end())
        {
            q[++tott].r=*it;
            q[tott].l=x;
            q[tott].d=dep[x];
            q[tott].opt=1;
        }
        if(it!=s[x].begin())
        {
            it--;
            q[++tott].l=*it;
            q[tott].r=x;
            q[tott].d=dep[x];
            q[tott].opt=1;
        }
    }
    s[x].insert(x);
    q[++tott].l=x;
    q[tott].r=x;
    q[tott].d=dep[x];
    q[tott].opt=1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y==fa||y==son[x]) continue;
        for(auto z:s[y])
        {
            it=s[x].lower_bound(z);
            if(it!=s[x].end())
            {
                q[++tott].r=*it;
                q[tott].l=z;
                q[tott].d=dep[x];
                q[tott].opt=1;
            }
            if(it!=s[x].begin())
            {
                it--;
                q[++tott].l=*it;
                q[tott].r=z;
                q[tott].d=dep[x];
                q[tott].opt=1;
            }
        }
        for(auto z:s[y])
        {
            s[x].insert(z);
        }
        s[y].clear();
    }
}
unordered_map<ll,int> mp;
int c[N];
inline int lowbit(int x){return -x&x;}
inline void add(int x,int k)
{
    for(;x<=n;x+=lowbit(x)) c[x]+=k;
    return ;
}
inline int ask(int x)
{
    int ans=0;
    for(;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}
int anss[N];
int main()
{
    // freopen("alley_ex3.in","r",stdin);
    // freopen("2.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<n;i++) 
    {
        int x,y;
        ll z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,0);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        q[++tott].l=l;
        q[tott].r=r;
        q[tott].opt=2;
        q[tott].d=i;
    }
    sort(q+1,q+tott+1);
    for(int i=1;i<=tott;i++)
    {
        // cout<<q[i].opt<<' '<<q[i].l<<' '<<q[i].r<<' '<<q[i].d<<'\n';
        if(q[i].opt==1)
        {
            if(mp.find(q[i].d)==mp.end())
            {
                mp[q[i].d]=q[i].l;
                add(q[i].l,1);
            }
            else if(mp[q[i].d]<q[i].l)    
            {
                add(mp[q[i].d],-1);
                add(q[i].l,1);
                mp[q[i].d]=q[i].l;
            }
        }
        else
        {
            anss[q[i].d]=ask(q[i].r)-ask(q[i].l-1);
        }
    }
    for(int i=1;i<=m;i++) cout<<anss[i]<<'\n';
    return 0;
}