bzoj 3653 谈笑风生——主席树

女爷i 2021-12-20 20:13 220阅读 0赞

题目：[https://www.lydsy.com/JudgeOnline/problem.php?id=3653][https_www.lydsy.com_JudgeOnline_problem.php_id_3653]

原来一直想怎么线段树合并。可是不会把角标挪一位。

查询的其实是子树内一段深度的点的 siz 和。因为是子树内，所以按 dfs 序建立主席树，角标是 dep ，值是 siz 。

注意 long long 。而且数组 \*19 就会 RE ，\*20就好了。不知为何。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define ll long long
    using namespace std;
    const int N=3e5+5,M=N*20;
    int n,Q,hd[N],xnt,to[N<<1],nxt[N<<1],siz[N],dfn[N],tim;
    int tot,rt[N],ls[M],rs[M],dep[N];
    ll sm[M];
    int rdn()
    {
      int ret=0;bool fx=1;char ch=getchar();
      while(ch>'9'||ch<'0'){
        if(ch=='-')fx=0;ch=getchar();}
      while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
      return fx?ret:-ret;
    }
    void write(ll x)
    {
      if(x<0)putchar('-'),x=-x;
      if(x<10){putchar(x+'0');return;}
      write(x/10); putchar(x%10+'0');
    }
    void add(int x,int y)
    {
      to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;
    }
    void dfs(int cr,int fa)
    {
      siz[cr]=1; dep[cr]=dep[fa]+1;
      for(int i=hd[cr],v;i;i=nxt[i])
        if((v=to[i])!=fa)dfs(v,cr),siz[cr]+=siz[v];
    }
    void mrg(int l,int r,int &cr,int pr,int p,int k)
    {
      cr=++tot; sm[cr]=sm[pr]+k;
      if(l==r)return;  int mid=l+r>>1;
      ls[cr]=ls[pr]; rs[cr]=rs[pr];
      if(p<=mid)mrg(l,mid,ls[cr],ls[pr],p,k);
      else mrg(mid+1,r,rs[cr],rs[pr],p,k);
    }
    void dfsx(int cr,int fa)
    {
      dfn[cr]=++tim; mrg(1,n,rt[dfn[cr]],rt[dfn[cr]-1],dep[cr],siz[cr]-1);
      for(int i=hd[cr],v;i;i=nxt[i])
        if((v=to[i])!=fa)dfsx(v,cr);
    }
    ll query(int l,int r,int cr,int pr,int L,int R)
    {
      if(l>=L&&r<=R)return sm[cr]-sm[pr];
      int mid=l+r>>1; ll ret=0;
      if(L<=mid)ret=query(l,mid,ls[cr],ls[pr],L,R);
      if(mid<R)ret+=query(mid+1,r,rs[cr],rs[pr],L,R);
      return ret;
    }
    int main()
    {
      n=rdn(); Q=rdn();
      for(int i=1,u,v;i<n;i++)
        {
          u=rdn(); v=rdn(); add(u,v); add(v,u);
        }
      dfs(1,0); dfsx(1,0);
      for(int i=1,p,k;i<=Q;i++)
        {
          p=rdn(); k=rdn();
          ll ans=(ll)min(k,dep[p]-1)*(siz[p]-1);
          if(siz[p]>1)
        ans+=query(1,n,rt[dfn[p]+siz[p]-1],rt[dfn[p]],dep[p]+1,dep[p]+k);
          write(ans); puts("");
        }
      return 0;
    }

转载于:https://www.cnblogs.com/Narh/p/9868575.html

[https_www.lydsy.com_JudgeOnline_problem.php_id_3653]: https://www.lydsy.com/JudgeOnline/problem.php?id=3653