Bzoj3653 谈笑风生

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 753 Solved: 295

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

Source

DFS序+可持久化线段树

相比前一道大新闻和后一道图样图森破来说，这题简直太特么友好了……但是膜多了果然有危害，昨天打CF的时候后台开着这题，把分数都续走了……（明明是自己蒻）

图样图森破正解是后缀数组LCP+st表什么的，理论AC，试着用后缀自动机写然而傻傻写不出，弃坑。

b可能是a的祖先也可能是a的子树。前者只需要dep[a]*(size[a]-1)得到答案，后者有些麻烦:对于每一个(a,b)对，答案等于b的子树size，。

刚开始的想法是用DFS序+树状数组统计，敲完DFS序以后开始懵逼，不会用树状数组统计答案……然后想到可持久化线段树。把DFS序作为时间轴，结点深度作为坐标，可以方便地统计出一个结点的所有子结点的size和，也就是后半部分答案。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<queue>
 6 #define LL long long
 7 using namespace std;
 8 const int mxn=300110;
 9 int read(){
10     int x=0,f=1;char ch=getchar();
11     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
13     return x*f;
14 }
15 struct edge{int v,nxt;}e[mxn<<1];
16 int hd[mxn],mct=0;
17 void add_edge(int u,int v){
18     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return;
19 }
20 int dep[mxn],sz[mxn];
21 //
22 int in[mxn],out[mxn];
23 int id[mxn],cnt=0;
24 int n,q;
25 struct node{
26     int l,r;LL sum;
27 }t[mxn*20];
28 int rt[mxn],tct=0;
29 int mx=0;
30 void DFS(int u,int fa){
31     in[u]=++cnt;
32     id[cnt]=u;
33     ++sz[u];
34     dep[u]=dep[fa]+1;
35     mx=max(mx,dep[u]);
36     for(int i=hd[u];i;i=e[i].nxt){
37         int v=e[i].v;
38         if(v==fa)continue;
39         DFS(v,u);
40         sz[u]+=sz[v];
41     }
42     out[u]=cnt;
43 }
44 void update(int p,int v,int l,int r,int x,int &rt){//p为深度 
45     rt=++tct;
46     if(x)t[rt]=t[x];
47     t[rt].sum+=v;
48     if(l==r)return;
49     int mid=(l+r)>>1;
50     if(p<=mid)update(p,v,l,mid,t[x].l,t[rt].l);
51     else update(p,v,mid+1,r,t[x].r,t[rt].r);
52     return;
53 }
54 LL query(int L,int R,int l,int r,int rt){
55     if(!rt)return 0;
56     if(L<=l && r<=R){return t[rt].sum;}
57     int mid=(l+r)>>1;
58     LL res=0;
59     if(L<=mid)res+=query(L,R,l,mid,t[rt].l);
60     if(R>mid)res+=query(L,R,mid+1,r,t[rt].r);
61     return res;
62 }
63 int main(){
64     int i,j,u,v;
65     n=read();q=read();
66     for(i=1;i<n;i++){
67         u=read();v=read();
68         add_edge(u,v);
69         add_edge(v,u);
70     }
71     DFS(1,0);
72     for(i=1;i<=cnt;i++){//插入值 
73         update(dep[id[i]],sz[id[i]]-1,1,mx,rt[i-1],rt[i]);
74     }
75     while(q--){
76         u=read();v=read();
77         LL ans=query(max(1,dep[u]+1),min(mx,dep[u]+v),1,mx,rt[out[u]]);
78         ans+=(LL)(min(dep[u]-1,v))*(sz[u]-1);
79         ans-=query(max(1,dep[u]+1),min(mx,dep[u]+v),1,mx,rt[in[u]-1]);
80         printf("%lld
",ans);
81     }
82     return 0;
83 }