BZOJ3653 & 洛谷3899：谈笑风生—

https://www.lydsy.com/JudgeOnline/problem.php?id=3653

https://www.luogu.org/problemnew/show/P3899

设 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) 满足：

a、 b 和 c 为 T 中三个不同的点，且 a 为 p 号节点；

a 和 b 都比 c 不知道高明到哪里去了；

a 和 b 谈笑风生。这里谈笑风生中的常数为给定的 k。

看到这题第一反应：woc点分治裸题233。

写了一回：woc点分治怎么写？？？

所以这就是为什么用主席树的原因了（并不

前两个条件只要固定了a和b我们就知道c的方案一定是a（或b，取决于谁深度大）的子树大小-1.

事实上对于一个节点，它周围可以谈笑风生的节点要么是它的祖先要么是它子树的点。

对于前者，处理dep数组之后就很好解决了。

对于后者，dfs序更新节点再树上主席树维护dep数组记录每个节点的子树大小-1（前缀和）。

查询的时候就是正常的主席树了。

PS：1.5h debug结果：思维定式，结果把主席树建成了和以前树上主席树一样的树就gg，错误请看代码。

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=3e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct node{

    int to,nxt;

}e[N*];

struct tree{

    int l,r;

    ll sum;

}tr[N*];

int cnt,n,q,head[N],sz[N],dep[N];

int rt[N],idx[N],tot,pool,maxd;

inline void add(int u,int v){

    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;

}

void insert(int y,int &x,int l,int r,int p,ll w){

    tr[x=++pool]=tr[y];

    tr[x].sum+=w;

    if(l==r)return;

    int mid=(l+r)>>;

    if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p,w);

    else insert(tr[y].r,tr[x].r,mid+,r,p,w);

}

ll query(int y,int x,int l,int r,int l1,int r1){

    if(r1<l||r<l1)return ;

    if(l1<=l&&r<=r1)return tr[x].sum-tr[y].sum;

    int mid=(l+r)>>;

    return query(tr[y].l,tr[x].l,l,mid,l1,r1)+

      query(tr[y].r,tr[x].r,mid+,r,l1,r1);

}

void dfs1(int u,int f,int d){

    idx[u]=++tot;

    sz[u]=;dep[u]=d;

    maxd=max(maxd,d);

    for(int i=head[u];i;i=e[i].nxt){

    int v=e[i].to;

    if(v==f)continue;

    dfs1(v,u,d+);

    sz[u]+=sz[v];

    }

}

void dfs2(int u,int f){

    insert(rt[idx[u]-],rt[idx[u]],,maxd,dep[u],sz[u]-);

    //错误点，曾经写成insert(rt[idx[f]],rt[idx[u]],1,maxd,dep[u],sz[u]-1);

    for(int i=head[u];i;i=e[i].nxt){

    int v=e[i].to;

    if(v==f)continue;

    dfs2(v,u);

    }

}

int main(){

    n=read(),q=read();

    for(int i=;i<n;i++){

    int u=read(),v=read();

    add(u,v);add(v,u);

    }

    dfs1(,,);dfs2(,);

    for(int i=;i<=q;i++){

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

    ll ans=(ll)(sz[p]-)*min(dep[p]-,k);

    ans+=query(rt[idx[p]-],rt[idx[p]+sz[p]-],,maxd,dep[p]+,dep[p]+k);

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

    }

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ3653 & 洛谷3899：谈笑风生——题解

最新文章

热门文章