luogu3899谈笑风生

https://www.zybuluo.com/ysner/note/1298140

题面

设\(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\)。

解析

题面真有趣

有一个很套路的树状数组离线做法：（我在这题的博客里提过一遍）

按照中序遍历\(DFS\)，每到一个点，先减去自己的子树以外的影响（树状数组询问一下），然后再把这个点加进树状数组。

这样当每个点的子树被遍历完时，用当前得到的答案，减去上一次得到的答案，就是自己的子树对答案的贡献。

既然上次我写了线段树合并，这次就离线算法舒服一下：

（然后因树状数组内上限设为\(n\)，\(GG\)了不知道多少回。。。）

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

#define re register

#define il inline

#define pb(a) push_back(a)

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

const int N=3e5+100;

int n,q,h[N],cnt,sz[N],d[N];

ll t[N],ans[N];

vector<int>Q[N],id[N];

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

il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}

il void mod(re int x,re int w){for(;x<=N-100;x+=x&-x) t[x]+=w;}

il ll que(re int x){if(x>=N-100) x=N-100;re ll res=0;for(;x;x-=x&-x) res+=t[x];return res;}

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

il void dfs(re int u,re int fa)

{

  d[u]=d[fa]+1;sz[u]=1;

  for(re int i=0;i<Q[u].size();++i) ans[id[u][i]]-=que(d[u]+Q[u][i]);

  for(re int i=h[u];i+1;i=e[i].nxt)

    {

      re int v=e[i].to;

      if(v==fa) continue;

      dfs(v,u);

      sz[u]+=sz[v];

    }

  for(re int i=0;i<Q[u].size();++i) ans[id[u][i]]+=que(d[u]+Q[u][i])+1ll*min(d[u]-1,Q[u][i])*(sz[u]-1);

  mod(d[u],sz[u]-1);

}

int main()

{

  memset(h,-1,sizeof(h));

  n=gi();q=gi();

  fp(i,1,n-1)

    {

      re int u=gi(),v=gi();

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

    }

  fp(i,1,q)

    {

      re int x=gi(),y=gi();

      Q[x].pb(y);id[x].pb(i);

    }

  dfs(1,0);

  fp(i,1,q) printf("%lld\n",ans[i]);

  return 0;

}

巴特西

luogu3899谈笑风生

https://www.zybuluo.com/ysner/note/1298140

题面

解析

最新文章

热门文章