注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3653]谈笑风生  

2015-05-14 15:32:54|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3653: 谈笑风生

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 240  Solved: 84
[Submit][Status][Discuss]

Description

设T 为一棵有根树,我们做如下的定义:
? 设a和b为T 中的两个不同节点。如果a是b的祖先,那么称“a比b不知道高明到哪里去了”。
? 设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数x,那么称“a 与b 谈笑风生”。
给定一棵n个节点的有根树T,节点的编号为1 到 n,根节点为1号节点。你需要回答q 个询问,询问给定两个整数p和k,问有多少个有序三元组(a;b;c)满足:
1. a、b和 c为 T 中三个不同的点,且 a为p 号节点;
2. a和b 都比 c不知道高明到哪里去了;
3. a和b 谈笑风生。这里谈笑风生中的常数为给定的 k。

Input

输入文件的第一行含有两个正整数n和q,分别代表有根树的点数与询问的个数。接下来n - 1行,每行描述一条树上的边。每行含有两个整数u和v,代表在节点u和v之间有一条边。
接下来q行,每行描述一个操作。第i行含有两个整数,分别表示第i个询问的p和k。

Output

输出 q 行,每行对应一个询问,代表询问的答案。

Sample Input

5 3 1 2 1 3 2 4 4 5 2 2 4 1 2 3

Sample Output

3 1 3

HINT

1<=P<=N
1<=K<=N
N<=300000
Q<=300000

Solution

如果b在a上面,ans+=size[a]*dep[a];
如果b在a下面,就是把满足条件的size[b]加起来,
于是将这颗树以dfs序展开,然后用可持久化线段树,以dep为关键字维护size值。

Code

/**************************************************************
    Problem: 3653
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:9720 ms
    Memory:149932 kb
****************************************************************/
 
#include<cstdio>
#define N 300010
typedef long long ll;
int n,m,et,la[N],L[N],R[N],q[N],cnt,tot,siz[N],x,y,vis[N],dep[N],d,p,k,rt[N],i;
struct T{int ls,rs;ll sum;}t[1<<23];
struct E{int to,nxt;}e[N<<1];
#define add(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void dfs(int x){
    vis[x]=1;q[L[x]=++cnt]=x;if(dep[x]>d)d=dep[x];
    for(;la[x];la[x]=e[la[x]].nxt)
    if(!vis[e[la[x]].to])dep[e[la[x]].to]=dep[x]+1,dfs(e[la[x]].to),siz[x]+=siz[e[la[x]].to]+1;
    R[x]=cnt;
}
int bt(int o,int l,int r){
    int now=++tot,mid=l+r>>1;t[now]=t[o];t[now].sum+=x;
    if(l==r)return now;
    if(y<=mid)t[now].ls=bt(t[o].ls,l,mid);
    else t[now].rs=bt(t[o].rs,mid+1,r);
    return now;
}
ll query(int o,int l,int r){
    if(x<=l&&r<=y)return t[o].sum;
    int mid=l+r>>1;ll ans=0;
    if(x<=mid)ans+=query(t[o].ls,l,mid);
    if(mid<y)ans+=query(t[o].rs,mid+1,r);
    return ans;
}
char B[1<<15],*S=B,*T=B,ch;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int main(){
    for(n=F(),m=F(),i=1;i<n;i++)x=F(),y=F(),add(x,y),add(y,x);
    for(dfs(1),i=1;i<=n;i++)x=siz[q[i]],y=dep[q[i]],rt[i]=bt(rt[i-1],0,d);
    for(;m--;){
        p=F(),k=F(),x=dep[p]+1,y=dep[p]+k;
        printf("%lld\n",1LL*siz[p]*(dep[p]<k?dep[p]:k)+query(rt[R[p]],0,d)-query(rt[L[p]],0,d));
    }
}
  评论这张
 
阅读(44)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018