[关闭]
@ysner 2018-09-30T00:35:02.000000Z 字数 1754 阅读 1947

luogu3899谈笑风生

线段树 线段树合并 树状数组


题面

为一棵有根树,我们做如下的定义:

给定一棵个节点的有根树,节点的编号为,根节点为号节点。你需要回答个询问,询问给定两个整数,问有多少个有序三元组满足:

解析

题面真有趣

有一个很套路的树状数组离线做法:(我在这题的博客里提过一遍)
按照中序遍历,每到一个点,先减去自己的子树以外的影响(树状数组询问一下),然后再把这个点加进树状数组。
这样当每个点的子树被遍历完时,用当前得到的答案,减去上一次得到的答案,就是自己的子树对答案的贡献。

既然上次我写了线段树合并,这次就离线算法舒服一下:
(然后因树状数组内上限设为了不知道多少回。。。)

  1. #include<iostream>
  2. #include<cmath>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #include<algorithm>
  7. #include<vector>
  8. #define ll long long
  9. #define re register
  10. #define il inline
  11. #define pb(a) push_back(a)
  12. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  13. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  14. using namespace std;
  15. const int N=3e5+100;
  16. int n,q,h[N],cnt,sz[N],d[N];
  17. ll t[N],ans[N];
  18. vector<int>Q[N],id[N];
  19. struct Edge{int to,nxt;}e[N<<1];
  20. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  21. il void mod(re int x,re int w){for(;x<=N-100;x+=x&-x) t[x]+=w;}
  22. 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;}
  23. il ll gi()
  24. {
  25. re ll x=0,t=1;
  26. re char ch=getchar();
  27. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  28. if(ch=='-') t=-1,ch=getchar();
  29. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  30. return x*t;
  31. }
  32. il void dfs(re int u,re int fa)
  33. {
  34. d[u]=d[fa]+1;sz[u]=1;
  35. for(re int i=0;i<Q[u].size();++i) ans[id[u][i]]-=que(d[u]+Q[u][i]);
  36. for(re int i=h[u];i+1;i=e[i].nxt)
  37. {
  38. re int v=e[i].to;
  39. if(v==fa) continue;
  40. dfs(v,u);
  41. sz[u]+=sz[v];
  42. }
  43. 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);
  44. mod(d[u],sz[u]-1);
  45. }
  46. int main()
  47. {
  48. memset(h,-1,sizeof(h));
  49. n=gi();q=gi();
  50. fp(i,1,n-1)
  51. {
  52. re int u=gi(),v=gi();
  53. add(u,v);add(v,u);
  54. }
  55. fp(i,1,q)
  56. {
  57. re int x=gi(),y=gi();
  58. Q[x].pb(y);id[x].pb(i);
  59. }
  60. dfs(1,0);
  61. fp(i,1,q) printf("%lld\n",ans[i]);
  62. return 0;
  63. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注