BZOJ3653

3653: 谈笑风生

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 1352 Solved: 588
[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。

1<=P<=N

1<=K<=N

N<=300000

Q<=300000

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

Hint:边要加双向

___________________________________________________________

DFS序+离线分层处理数据

求书上符合条件的三元组（a,b,c）的数量。a为给定点，b点到a点的距离不超过一直量k，且a,b为祖孙的关系，c为a、b的子孙。

根据a、b的关系分成两类：

1、b为a的祖先。那么b的可能有min(k,dep[a]-1)种，而c的可能为siz[a]-1种，那么两个值的成绩就是答案。

2、b为a的子孙，那么b的可能为所有与a深度差不超过k的子孙点,而c点的肯为对应每个b点的子孙树（siz[b]-1）

第一种情况比较好求，深搜可以求出对应dep[]和siz[]，然后乘起来就好了

第二种情况比较麻烦，因为有多问，没问要遍历所有b的可能点，然后求对应c点的可能（siz[b]-1）之和。这个复杂度太高，不可完成。

所以离线，把所有问题保存起来，其中每一问b点的最深深度是关键，用它对问题进行重新排序。这样一层一层的更新每个点的子孙数量（-1），用树状数组维护，但已经更新到当前这一问的最深深度时，用树状数组求出对应子树的和，就是答案。

按照黄学长的说法，离线比较简单，但是我没有怎么学过离线的算法，所以理解了好一会儿，很巧妙！膜拜一下！

___________________________________________________________

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int maxn=3e5+10;
  4 int n,m;
  5 struct edge
  6 {
  7     int u,v,nxt;
  8 }e[maxn<<1];
  9 int head[maxn],js;
 10 void addage(int u,int v)
 11 {
 12     e[++js].u=u;e[js].v=v;
 13     e[js].nxt=head[u];head[u]=js;
 14 }
 15 int dep[maxn],lt[maxn],rt[maxn],cnt,siz[maxn],depf[maxn];
 16 void dfs(int u,int fa)
 17 {
 18     dep[u]=dep[fa]+1;
 19     lt[u]=++cnt;
 20     siz[u]=1;
 21     for(int i=head[u];i;i=e[i].nxt)
 22     {
 23         int v=e[i].v;
 24         if(v==fa)continue;
 25         dfs(v,u);
 26         depf[u]=max(depf[u],depf[v]);
 27         siz[u]+=siz[v];
 28     }
 29     depf[u]++;
 30     rt[u]=cnt;
 31 }
 32 int Q[maxn],t,h;
 33 void bfs()
 34 {
 35     h=0;
 36     Q[t=1]=1;
 37     while(t>h)
 38     {
 39         int u=Q[++h];
 40         for(int i=head[u];i;i=e[i].nxt)
 41         {
 42             int v=e[i].v;
 43             if(dep[v]<dep[u])continue;
 44             Q[++t]=v;
 45         }
 46     }
 47 }
 48 struct que
 49 {
 50     int p,k,dp,id;
 51     long long ans;
 52 }q[maxn];
 53 bool cmp(que a,que b)
 54 {
 55     return a.dp<b.dp;
 56 }
 57 long long da[maxn];
 58 long long sz[maxn];
 59 void change(int x,int y)
 60 {
 61     for(int i=x;i<=n;i+=i&(-i))sz[i]+=y;
 62 }
 63 long long query(int x)
 64 {
 65     long long ans=0;
 66     for(int i=x;i>0;i-=i&(-i))ans+=sz[i];
 67     return ans;
 68 }
 69 int main()
 70 {
 71     scanf("%d%d",&n,&m);
 72     for(int u,v,i=1;i<n;++i)
 73     {
 74         scanf("%d%d",&u,&v);
 75         addage(u,v);addage(v,u);
 76     }
 77     dfs(1,0);
 78     bfs();
 79     for(int i=1;i<=m;++i)
 80     {
 81         scanf("%d%d",&q[i].p,&q[i].k);
 82         q[i].dp=min(dep[q[i].p]+q[i].k,depf[q[i].p]+dep[q[i].p]-1);
 83         q[i].id=i;
 84         q[i].ans=1LL*min(dep[q[i].p]-1,q[i].k)*(siz[q[i].p]-1);
 85     }
 86     sort(q+1,q+1+m,cmp);
 87     int cur=1;
 88     for(int i=1;i<=m;++i)
 89     {
 90         int deep=q[i].dp;
 91         while(Q[cur]!=0 && dep[Q[cur]]<=deep)
 92         {
 93             change(lt[Q[cur]],siz[Q[cur]]-1);
 94             cur++;
 95         }
 96         q[i].ans+=query(rt[q[i].p])-query(lt[q[i].p]);
 97     }
 98     for(int i=1;i<=m;++i)da[q[i].id]=q[i].ans;
 99     for(int i=1;i<=m;++i)printf("%lld
",da[i]);
100     return 0;
101 }

View Code