P7880

cwfxlh · 2023-11-25 10:34:16 · 题解

P7880

考虑一个点在什么时候会被选作 lca。将其子树内的所有点列出来，表示为 (w_x,col_x) 的形式，其中 col_x 表示它在哪个子树里面，w_x 表示编号。按 w_x 从小到大排序，如果 col_x\not= col_{x+1}，且 [w_x,w_{x+1}]\in[l,r]，则这个点会被选中。

分析一下这样的点对的个数，发现我们可以使用启发式合并来合并子树信息，于是点对数量是 n\log n 级别的。

求出所有点对后，我们将其按对应点的颜色分类。对于一种颜色，如果点 (l,r) 在其点对构成的折线的上方，则加入这种颜色。于是对于每一种颜色，我们将其维护成若干个矩形加，扫描线单点查询即可。复杂度 O(n\log^2n+m\log n)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,qq[500003][2],ans[500003],dep[200003],col[200003],F[200003];
int stk[500003],tot;
map<int,int>mp;
set<int>R[200003];
int totr,ys[200003],sz[200003];
struct Que{
    int v1;
    int v2;
    int v3;
}Q[4000003];
int totQ;
int k1,k2,k3,k4,k5,k6,k7,k8,k9;
vector<pair<int,int> >E[200003];
vector<pair<int,int> >lst[200003];
void dfs(int now){
    for(auto i:E[now]){
        if(i.first==F[now])continue;
        F[i.first]=now;
        dep[i.first]=dep[now]+i.second;
        dfs(i.first);
    }
    return;
}
void Merge(int X,int Y,int mk){
    auto p=R[X].begin();
    for(auto i:R[Y]){
        p=R[X].lower_bound(i);
        if(p!=R[X].end()&&(*p)>i)lst[mk].emplace_back(make_pair(i,(*p)));
        if(p==R[X].begin())continue;
        p--;
        if(p!=R[X].end()&&(*p)<i)lst[mk].emplace_back(make_pair((*p),i));
    }
    for(auto i:R[Y])R[X].insert(i);
    R[Y].clear();
    sz[X]+=sz[Y];
    sz[Y]=0;
    return;
}
void dfs2(int now){
    lst[col[now]].emplace_back(make_pair(now,now));
    ys[now]=++totr;
    R[totr].insert(now);
    sz[totr]=1;
    for(auto i:E[now]){
        if(i.first==F[now])continue;
        dfs2(i.first);
        if(sz[ys[now]]<sz[ys[i.first]])swap(ys[now],ys[i.first]);
        Merge(ys[now],ys[i.first],col[now]);
    }
    return;
}
vector<int>lstq[200003];
vector<int>lstop[200003];
int TreeAr[200003];
int lowbit(int X){return (X&(-X));}
void add(int l,int r){
    for(int i=l;i<=n+10;i+=lowbit(i))TreeAr[i]++;
    for(int i=r+1;i<=n+10;i+=lowbit(i))TreeAr[i]--;
    return;
}
int Query(int wz){
    int ret=0;
    for(int i=wz;i;i-=lowbit(i))ret+=TreeAr[i];
    return ret;
}
int read(){
    int xx=0,ff=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')ff=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')xx=xx*10+ch-'0',ch=getchar();
    return xx*ff;
}
void write(int xx){
    if(xx<0)putchar('-'),xx=-xx;
    if(xx>9)write(xx/10);
    putchar(xx%10+'0');
    return;
}
signed main(){
    n=read();
    m=read();
    for(int i=1;i<n;i++){
        k1=read();
        k2=read();
        k3=read();
        E[k1].emplace_back(make_pair(k2,k3));
        E[k2].emplace_back(make_pair(k1,k3));
    }
    for(int i=1;i<=m;i++){
        qq[i][0]=read();
        qq[i][1]=read();
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        if(mp[dep[i]]==0){
            stk[++tot]=dep[i];
            mp[dep[i]]=1;
        }
    }
    sort(stk+1,stk+tot+1);
    for(int i=1;i<=tot;i++)mp[stk[i]]=i;
    for(int i=1;i<=n;i++)col[i]=mp[dep[i]];
    dfs2(1);
    for(int i=1;i<=tot;i++){
        sort(lst[i].begin(),lst[i].end());
        k7=n+10;
        for(int j=(int)(lst[i].size())-1;j>=0;j--){
            if(k7<=lst[i][j].second)continue;
            Q[++totQ].v1=lst[i][j].first;
            Q[totQ].v2=lst[i][j].second;
            Q[totQ].v3=k7-1;
            k7=lst[i][j].second;
        }
    }
    for(int i=1;i<=totQ;i++)lstop[Q[i].v1].emplace_back(i);
    for(int i=1;i<=m;i++)lstq[qq[i][0]].emplace_back(i);
    for(int i=n;i;i--){
        for(auto j:lstop[i])add(Q[j].v2,Q[j].v3);
        for(auto j:lstq[i])ans[j]=Query(qq[j][1]);
    }
    for(int i=1;i<=m;i++){
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}