洛谷3899 [湖南集训]谈笑风生

Luogu

分析

线段树合并。

显然只有两种情况: $a$ 比 $b$ 不知道高明到哪去了、 $b$ 比 $a$ 不知道高明到哪去了。

第二种比较简单。设 $a$ 的深度为 $dep[a]$ ,子树大小为 $sz[a]$ ,答案就是 $\min\{dep[a]-1,k\}\times (sz[a]-1)$ 。

第一种的话,可以在 $a$ 的子树中随便选一个点和 $a$ 谈笑风生的点作为 $b$ ,然后在 $b$ 的子树中随便选一个作为 $c$ 。答案就是 $\sum\limits_{dep[a]+b\geq dep[b]}sz[b]-1$ 。

每个点维护一颗以深度为下标、$sz-1$ 为权值的权值线段树,然后这个东西就很容易算了。

至于这个线段树怎么求?每次向上合并就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300000+10;

struct Edge { int v,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,Q;

//线段树

int rt[N],tot=0;
int ls[N*20],rs[N*20],sum[N*20];

inline void pushup(int o) { sum[o]=sum[ls[o]]+sum[rs[o]]; }

inline void modify(int& o,int l,int r,int p,int v) {
    if (!o) o=++tot;
    if (l==r) { sum[o]+=v; return; }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls[o],l,mid,p,v);
    else modify(rs[o],mid+1,r,p,v);
    pushup(o);
}

inline int query(int& o,int l,int r,int ql,int qr) {
    if (!o) return 0;
    if (ql<=l&&r<=qr) return sum[o];
    int mid=(l+r)>>1,res=0;
    if (ql<=mid) res+=query(ls[o],l,mid,ql,qr);
    if (qr>mid) res+=query(rs[o],mid+1,r,ql,qr);
    return res;
}

inline int merge(int p,int q) {
    if (!p||!q) return p+q;
    int t=++tot;
    sum[t]=sum[p]+sum[q];
    ls[t]=merge(ls[p],ls[q]);
    rs[t]=merge(rs[p],rs[q]);
    return t;
}

int dep[N],sz[N];

inline void dfs(int u,int fa) {
    dep[u]=dep[fa]+1,sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u); sz[u]+=sz[v],rt[u]=merge(rt[u],rt[v]);
    }
    modify(rt[u],1,n,dep[u],sz[u]-1);
}

signed main() {
    n=read(),Q=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    while (Q--) {
        int p=read(),k=read();
        printf("%lld\n",min(dep[p]-1,k)*(sz[p]-1)+query(rt[p],1,n,dep[p]+1,dep[p]+k));
    }
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 03 PM

发表评论