BZOJ3653: 谈笑风生

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3653

题解：稍微思考可以知道只要求x子树内dep[y]-dep[x]<=k 的 s[y]-1 之和即可。

我刚开始想得是线段树/树状数组套 treap，显然可做，但是nlog^2n ，显然要T。。。

于是我们转化思路，直接用一维dep来建主席树，这样子树内的信息都是O（1）就可以知道了。

查询区间和只要和普通线段树一样即可O（logn）。

真是一道好题！

代码：

  1 #include<cstdio>
  2 
  3 #include<cstdlib>
  4 
  5 #include<cmath>
  6 
  7 #include<cstring>
  8 
  9 #include<algorithm>
 10 
 11 #include<iostream>
 12 
 13 #include<vector>
 14 
 15 #include<map>
 16 
 17 #include<set>
 18 
 19 #include<queue>
 20 
 21 #include<string>
 22 
 23 #define inf 1000000000
 24 
 25 #define maxn 300000+5
 26 
 27 #define maxm 6000000+5
 28 
 29 #define eps 1e-10
 30 
 31 #define ll long long
 32 
 33 #define pa pair<int,int>
 34 
 35 #define for0(i,n) for(int i=0;i<=(n);i++)
 36 
 37 #define for1(i,n) for(int i=1;i<=(n);i++)
 38 
 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)
 40 
 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)
 42 
 43 #define for4(i,x) for(int i=head[x],y=e[i].go;i;i=e[i].next,y=e[i].go)
 44 
 45 #define for5(n,m) for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
 46 
 47 #define mod 1000000007
 48 
 49 using namespace std;
 50 
 51 inline int read()
 52 
 53 {
 54 
 55     int x=0,f=1;char ch=getchar();
 56 
 57     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 58 
 59     while(ch>='0'&&ch<='9'){x=10*x+ch-'0';ch=getchar();}
 60 
 61     return x*f;
 62 
 63 }
 64 int n,m,head[maxn],tot,cnt,ti,id[maxn],pos[maxn][2],rt[maxn],s[maxn],dep[maxn];
 65 struct edge{int go,next;}e[2*maxn];
 66 int ls[maxm],rs[maxm];
 67 ll sum[maxm];
 68 inline void add(int x,int y)
 69 {
 70     e[++tot]=(edge){y,head[x]};head[x]=tot;
 71     e[++tot]=(edge){x,head[y]};head[y]=tot;
 72 }
 73 inline void dfs(int x)
 74 {
 75     id[pos[x][0]=++ti]=x;s[x]=1;
 76     for4(i,x)if(!pos[y][0])dep[y]=dep[x]+1,dfs(y),s[x]+=s[y];
 77     pos[x][1]=ti;
 78 }
 79 inline void update(int l,int r,int x,int &y,int z,int w)
 80 {
 81     y=++cnt;
 82     sum[y]=sum[x]+(ll)w;
 83     if(l==r)return;
 84     int mid=(l+r)>>1;
 85     ls[y]=ls[x];rs[y]=rs[x];
 86     if(z<=mid)update(l,mid,ls[x],ls[y],z,w);else update(mid+1,r,rs[x],rs[y],z,w);
 87 }
 88 inline ll query(int x,int y,int l,int r,int xx,int yy)
 89 {
 90     if(l==xx&&r==yy)return sum[y]-sum[x];
 91     int mid=(l+r)>>1;
 92     if(yy<=mid)return query(ls[x],ls[y],l,mid,xx,yy);
 93     else if(xx>mid)return query(rs[x],rs[y],mid+1,r,xx,yy);
 94     else return query(ls[x],ls[y],l,mid,xx,mid)+query(rs[x],rs[y],mid+1,r,mid+1,yy);
 95 }
 96 
 97 int main()
 98 
 99 {
100 
101     freopen("input.txt","r",stdin);
102 
103     freopen("output.txt","w",stdout);
104 
105     n=read();m=read();
106     for1(i,n-1)add(read(),read());
107     dfs(1);
108     for1(i,n)update(0,n,rt[i-1],rt[i],dep[id[i]],s[id[i]]-1);
109     while(m--)
110     {
111         int x=read(),y=read();
112         printf("%lld
",(ll)(s[x]-1)*min(dep[x],y)+query(rt[pos[x][0]-1],rt[pos[x][1]],0,n,dep[x]+1,min(dep[x]+y,n)));
113     }
114 
115     return 0;
116 
117 }

View Code

一开始一直WA是因为没有把0建到主席树里。