题解 P3899 【[湖南集训]谈笑风生】

· · 题解

这道题看到大家都用主席树或者权值线段树等等，其实完全没有必要呀orz

只要稍微想想就能发现，它其实可以转变为一个简单的二维数点问题。

设dep_i为i节点的深度（根节点深度为0），sz_i为i节点子树大小

对于询问(p,k),我们将(a,b,c)这一三元组分为两种情况：

1)b是a的父亲。显然，这时c可以是a子树内任何一个节点。

此时答案为(sz_p-1)\times min(dep_p,k)，因为有min(dep_p,k)个合法的b是a的父亲

2)b是a的儿子。显然，只有dep_b\in [dep_a+1,dep_a+k]时，这才是一个合法的b。

而对每个b，它能贡献sz_b-1个答案。

而如何判断每个b是否在a的子树内呢？

dfs序

设rev_i表示i节点在dfs序中，在第rev_i次时被访问到

则[rev_i,rev_i+sz_i-1]为节点i的子树编号。

那么，对于节点a，所有满足dep_b\in [dep_a+1,dep_a+k]且rev_b\in[rev_a+1,rev_a+sz_a-1]的b均为合法的b。

想到了什么？

如果我们以rev作为x轴，dep作为y轴，建立平面直角坐标系，则每个节点i可以被抽象成一个点(rev_i,dep_i)，并且有sz_i-1的权值。

而每次询问，就可以被抽象成一个矩形，查询的是矩形内部所有点的权值和。

并且，这道题可以离线。

然后，就可以愉快地用树状数组进行二维数点了。

复杂度O(nlog_2n)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,head[300100],cnt,dep[300100],rev[300100],tot,sz[300100],res[300100],BIT[300100];
struct Edge{
    int to,next;
}edge[600100];
int ae(int u,int v){
    edge[cnt].to=v,edge[cnt].next=head[u],head[u]=cnt++;
}
void dfs(int x,int fa){
    rev[x]=++tot,sz[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa)dep[edge[i].to]=dep[x]+1,dfs(edge[i].to,x),sz[x]+=sz[edge[i].to];
}
struct Point{
    int u,v,w;
    Point(int a=0,int b=0,int c=0){
        u=a,v=b,w=c;
    }
    friend bool operator <(const Point &x,const Point &y){
        return x.v<y.v;
    }
}p[300100];
struct Query{
    int x1,x2,y,id;
    Query(int a=0,int b=0,int c=0,int d=0){
        x1=a,x2=b,y=c,id=d;
    }
    friend bool operator <(const Query &x,const Query &y){
        return x.y<y.y;
    }
}q[600100];
int lowbit(int x){
    return x&-x;
}
void add(int x,int val){
    while(x<=n)BIT[x]+=val,x+=lowbit(x);
}
int ask(int x){
    int sum=0;
    while(x)sum+=BIT[x],x-=lowbit(x);
    return sum;
}
signed main(){
    scanf("%lld%lld",&n,&m),memset(head,-1,sizeof(head));
    for(int i=1,x,y;i<n;i++)scanf("%lld%lld",&x,&y),ae(x,y),ae(y,x);
    dfs(1,0);
    for(int i=1;i<=n;i++)p[i]=Point(rev[i],dep[i],sz[i]-1);
    for(int i=1,x,y;i<=m;i++){
        scanf("%lld%lld",&x,&y);
        res[i]+=(sz[x]-1)*min(dep[x],y);
        q[(i<<1)-1]=Query(rev[x],rev[x]+sz[x]-1,dep[x],-i);
        q[(i<<1)]=Query(rev[x],rev[x]+sz[x]-1,dep[x]+y,i);
    }
    sort(p+1,p+n+1);
    sort(q+1,q+(m*2)+1);
    for(int i=1,j=1;i<=(m*2);i++){
        while(j<=n&&p[j].v<=q[i].y)add(p[j].u,p[j].w),j++;
        if(q[i].id>0)res[q[i].id]+=ask(q[i].x2)-ask(q[i].x1);
        else res[q[i].id]-=ask(q[i].x2)-ask(q[i].x1);
    }
    for(int i=1;i<=m;i++)printf("%lld\n",res[i]);
    return 0;
}