【BZOJ-3653】谈笑风生 DFS序 + 可持久化线段树

3653: 谈笑风生

Time Limit: 20 Sec Memory Limit: 512 MB
Submit: 628 Solved: 245
[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

Source

Solution

答案显然是$(size[x]-1)*min(deep[x],K)+\sum_{dis(x,y)<=K,y\epsilon x}^{y}(size[y]-1)$

考虑求后面那些东西，可以利用可持久化线段树来做

用deep作为下标，维护size。

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 300010

#define LL long long

int N,Q;

struct EdgeNode{int next,to;}edge[MAXN<<];

int head[MAXN],cnt=;

void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);}

int deep[MAXN],size[MAXN],pl[MAXN],pr[MAXN],pre[MAXN],dfn,maxd;

void DFS(int now,int last)

{

    pl[now]=++dfn; pre[dfn]=now; size[now]=;

    maxd=max(maxd,deep[now]);

    for (int i=head[now]; i; i=edge[i].next)

        if (edge[i].to!=last)

            {

                deep[edge[i].to]=deep[now]+;

                DFS(edge[i].to,now);

                size[now]+=size[edge[i].to];

            }

    pr[now]=dfn;

}

struct SegmentTreeNode{int ls,rs; LL sum;}tree[MAXN*];

int root[MAXN],sz;

void Update(int &now,int last,int l,int r,int pos,int val)

{

    now=++sz;

    tree[now].sum=tree[last].sum+val;

    if (l==r) return;

    int mid=(l+r)>>;

    tree[now].ls=tree[last].ls,tree[now].rs=tree[last].rs;

    if (pos<=mid) Update(tree[now].ls,tree[last].ls,l,mid,pos,val);

            else  Update(tree[now].rs,tree[last].rs,mid+,r,pos,val);

}

LL Query(int now,int l,int r,int L,int R)

{

    if (!now) return 0LL;

    if (L==l && R==r) return tree[now].sum;

    int mid=(l+r)>>;

    if (R<=mid) return Query(tree[now].ls,l,mid,L,R);

    else if (L>mid) return Query(tree[now].rs,mid+,r,L,R);

    else return Query(tree[now].ls,l,mid,L,mid)+Query(tree[now].rs,mid+,r,mid+,R);

}

int main()

{

    N=read(),Q=read();

    for (int x,y,i=; i<=N-; i++) x=read(),y=read(),InsertEdge(x,y);

    DFS(,);

//    for (int i=1; i<=N; i++)

//        printf("%d [%d , %d] %d %d\n",pre[i],pl[pre[i]],pr[pre[i]],size[pre[i]],deep[pre[i]]);

    for (int i=; i<=N; i++) Update(root[i],root[i-],,maxd,deep[pre[i]],size[pre[i]]-);

    for (int i=; i<=Q; i++)

        {

            int p=read(),K=read();

            LL ans=0LL;

            ans=(LL)(size[p]-)*min(deep[p],K)+Query(root[pr[p]],,maxd,deep[p]+,deep[p]+K)-Query(root[pl[p]-],,maxd,deep[p]+,deep[p]+K);

            printf("%lld\n",ans);

        }

    return ;

}

被Char哥-拍死了

秒客网