一些闲话

这题方法好多啊QAQ，离线有BIT、长链剖分，在线有线段树合并，主席树等。

要我出题绝对不可能放离线过。。。

题面链接

权限题诶

洛谷

题意简述

简单的看一下题意，就是给定\(a\)，求任何一个距\(a\)距离不超过给定的\(k\)的\(b\)，然后求一个\(c\)使得是\(a,b\)的后代。

sol

我相信你已经看出来了，\(abc\)在一条直上直下的链上，不过这并没有什么用。我们考虑当\(b\)是\(a\)的祖先时，\(a\)子树内所有除它自己以外的点都可以做\(c\)这个可以直接统计。当\(a\)是\(b\)的祖先时，\(b\)子树内所有除它以外的点都可以做\(c\)。那么每个节点搞一个权值线段树维护一下就可以辣。然后显然这个空间复杂度会爆炸，于是就可以愉快的线段树合并辣。

#include<vector>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gt getchar()

#define ll long long

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

inline int in()

{

    int k=0;char ch=gt;

    while(ch<'-')ch=gt;

    while(ch>'-')k=k*10+ch-'0',ch=gt;

    return k;

}

const int N=600005;

std::vector<int>Q[N],id[N];

using std::min;

using std::max;

struct node

{

    ll siz;int lc,rc;

}t[N*30];

int tot,opt;

ll query(int L,int R,int l,int r,int x)

{

    if(!x)return 0;

    if(L<=l&&r<=R)return t[x].siz;

    int mid=l+r>>1;ll res=0;

    if(mid>=L)res+=query(L,R,l, mid ,t[x].lc);

    if(mid< R)res+=query(L,R,mid+1,r,t[x].rc);

    return res;

}

void upd(int l,int r,int pos,int &x,int v)

{

    if(!x)x=++tot;t[x].siz+=v;

    if(l==r)return;

    int mid=l+r>>1;

    if(mid>=pos)upd(l,mid,pos,t[x].lc,v);

    else upd(mid+1,r,pos,t[x].rc,v);

}

int merge(int u,int v,int l,int r)

{

    if(!u||!v)return u|v;

    int mid=l+r>>1,x=++tot;

    t[x].siz=t[u].siz+t[v].siz;

    t[x].lc=merge(t[u].lc,t[v].lc,l, mid );

    t[x].rc=merge(t[u].rc,t[v].rc,mid+1,r);

    return x;

}

int siz[N],rt[N],a[N],b[N],fa[N],head[N],to[N],nxt[N],cnt,sz,dep[N];

ll ans[N];

inline void add(int u,int v)

{

    to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;

    to[++cnt]=u,nxt[cnt]=head[v],head[v]=cnt;

}

void dfs(int u,int pa=0)

{

    dep[u]=dep[pa]+1;siz[u]=1;//printf("u=%d pa=%d\n",u,pa);

    for(int i=head[u];i;i=nxt[i])

        if(to[i]!=pa)

            dfs(to[i],u),siz[u]+=siz[to[i]];

    upd(1,sz,dep[u],rt[u],siz[u]-1);

    if(pa)rt[pa]=merge(rt[pa],rt[u],1,sz);

}

int main()

{

    int n=in(),q=in();sz=n;

    for(int i=1;i<n;++i)add(in(),in());

    dfs(1);

    for(int i=1;i<=q;++i)

    {

        int x=in(),y=in();

        printf("%lld\n",query(dep[x]+1,dep[x]+y,1,n,rt[x])+1ll*(siz[x]-1)*min(dep[x]-1,y));

    }

    return 0;

}