BZOJ3653: 谈笑风生【主席树】

3653: 谈笑风生

【题目描述】

传送门

【题解】

题目描述是给你A,问你A、B是C的父亲的方案数。
首先我们肯定会想到B要么是A的祖先,要么是A的儿子。
如果是祖先的话好办,直接就可以算了。
但是麻烦的是儿子的情况,问题也就转化成了如何快速得到一棵树上,深度不超过K的权值和。
那么可以将树强制转成线段,然后套主席树就可以了。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=300005;
typedef long long LL;
int n,m,cnt,tot,P[MAXN],Siz[MAXN],Dfn[MAXN],Dep[MAXN];LL Sum[MAXN],Tre[MAXN*20];
int T[MAXN],LT[MAXN*20],RT[MAXN*20];
struct Edge{
    int tot,lnk[MAXN],son[MAXN<<1],nxt[MAXN<<1];
    void Add(int x,int y){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
}E;
#include<cctype>
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=ret*10+ch-48;
    return f?ret:-ret;
}
void DFS(int x,int fa){
    Dep[x]=Dep[fa]+1;P[Dfn[x]=++cnt]=x;Siz[x]=1;
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(E.son[j]!=fa) DFS(E.son[j],x),Sum[x]+=Sum[E.son[j]],Siz[x]+=Siz[E.son[j]];
    Sum[x]+=Siz[x]-1;
}
void Insert(int lst,int &x,int L,int R,int D,LL p){
    x=++tot;Tre[x]=Tre[lst]+p,LT[x]=LT[lst],RT[x]=RT[lst];
    if(L<R){
        int mid=(R+L)>>1;
        if(D<=mid) Insert(LT[lst],LT[x],L,mid,D,p);
        else Insert(RT[lst],RT[x],mid+1,R,D,p);
    }
}
LL Query(int u,int v,int L,int R,int D){
    if(L==R) return Tre[v]-Tre[u];
    int mid=(R+L)>>1;
    if(D<=mid) return Query(LT[u],LT[v],L,mid,D);
    else return Query(RT[u],RT[v],mid+1,R,D);
}
int main(){
    n=read(),m=read();
    for(int i=1,x,y;i<n;i++) x=read(),y=read(),E.Add(x,y),E.Add(y,x);
    DFS(1,0);
    for(int i=1;i<=n;i++) Insert(T[i-1],T[i],1,MAXN-5,Dep[P[i]],Sum[P[i]]);
    for(int i=1;i<=m;i++){
        int A=read(),K=read();LL Ans=0;
        Ans+=(LL)((LL)Siz[A]-1ll)*min(Dep[A]-1,K);
        Ans+=Sum[A]-Siz[A]+1-Query(T[Dfn[A]-1],T[Dfn[A]+Siz[A]-1],1,MAXN-5,Dep[A]+K+1);
        printf("%lld\n",Ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部