首页 > 其他 > 详细

【刷题】BZOJ 3653 谈笑风生

时间:2018-09-21 22:06:28      阅读:190      评论:0      收藏:0      [点我收藏+]

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:边要加双向

Solution

显然存在两种情况:

  1. \(a\)\(b\) 下面,这样就是 \(a\) 的除去自己的子树大小乘上 \(k\)\(a\) 深度的值小者。这个很显然嘛。
  2. \(a\)\(b\) 上面,这种情况,设计dp,\(f[i][j]\) 代表第 \(i\) 个点,其往下距离 \(i\) 长度 \(j\) 的点的除自己之外的子树大小和。那么答案就是 \(\sum_{i=1}^kf[p][i]\) 。发现这个dp与深度有关,所以长链剖分优化。然后因为还要求一个前缀和,所以要在dp时处理好。因为这个长链剖分dp只有加没有删,所以可以维护后缀和,答案差分算就好了。

综合上面两种情况,先把所有的询问挂在点上,然后dp统计答案

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define REP(a,b,c) for(register int a=(b),a##end=(c);a<=a##end;++a)
#define DEP(a,b,c) for(register int a=(b),a##end=(c);a>=a##end;--a)
const int MAXN=300000+10;
int n,q,e,beg[MAXN],nex[MAXN<<1],to[MAXN<<1],dep[MAXN],size[MAXN],hson[MAXN],Mxdep[MAXN],top[MAXN],cnt,id[MAXN];
ll ans[MAXN];
std::deque<ll> f[MAXN];
std::vector< std::pair<int,int> > V[MAXN];
template<typename T> inline void read(T &x)
{
    T data=0,w=1;
    char ch=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
    x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
    to[++e]=y;
    nex[e]=beg[x];
    beg[x]=e;
}
inline void dfs1(int x,int p)
{
    dep[x]=dep[p]+1;Mxdep[x]=dep[x];hson[x]=x;
    for(register int i=beg[x];i;i=nex[i])
        if(to[i]==p)continue;
        else
        {
            dfs1(to[i],x);
            if(Mxdep[to[i]]>Mxdep[x])hson[x]=to[i],Mxdep[x]=Mxdep[to[i]];
        }
}
inline void dfs2(int x,int p,int tp)
{
    top[x]=tp;
    if(hson[x]!=x)dfs2(hson[x],x,tp);
    for(register int i=beg[x];i;i=nex[i])
        if(to[i]==p||to[i]==hson[x])continue;
        else dfs2(to[i],x,to[i]);
}
#define ft first
#define sd second
inline void dfs(int x,int p)
{
    if(hson[x]==x)
    {
        id[x]=++cnt;
        f[id[x]].resize(dep[x]-dep[top[x]]);
        return ;
    }
    dfs(hson[x],x);
    id[x]=id[hson[x]];size[x]+=size[hson[x]]+1;
    ll now=size[hson[x]];
    f[id[x]].push_front(0);
    for(register int i=beg[x];i;i=nex[i])
        if(to[i]==p||to[i]==hson[x])continue;
        else
        {
            dfs(to[i],x);
            now+=size[to[i]];size[x]+=size[to[i]]+1;
            REP(j,1,Mxdep[to[i]]-dep[to[i]])f[id[x]][j]+=f[id[to[i]]][j-1];
        }
    f[id[x]][0]=f[id[x]][1]+now;
    REP(i,0,V[x].size()-1)
    {
        std::pair<int,int> pr=V[x][i];
        int ps=min(Mxdep[x]-dep[x],pr.sd-1);
        ans[pr.ft]=1ll*min(dep[x]-1,pr.sd)*size[x]+f[id[x]][0]-f[id[x]][ps+1];
    }
}
#undef ft
#undef sd
int main()
{
    read(n);read(q);
    REP(i,1,n-1)
    {
        int u,v;read(u);read(v);
        insert(u,v);insert(v,u);
    }
    REP(i,1,q)
    {
        int p,k;read(p);read(k);
        V[p].push_back(std::make_pair(i,k));
    }
    dfs1(1,0);dfs2(1,0,1);dfs(1,0);
    REP(i,1,q)printf("%lld\n",ans[i]);
    return 0;
}

【刷题】BZOJ 3653 谈笑风生

原文:https://www.cnblogs.com/hongyj/p/9688374.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!