[关闭]
@ysner 2018-10-22T11:30:48.000000Z 字数 2530 阅读 1614

[学习笔记]dsu on a tree（如何远离线段树合并）

dsu_on_a_tree 启发式合并

背景

这玩意来源于一种有局限性的算法。

有一种广为人知的，树上离线维护子树信息的做法。
（可以参照luogu3605 [USACO17JAN]Promotion Counting晋升者计数)

用树状数组维护贡献，并把询问挂在点上。
先遍历整棵树。
在进入一个点时，在询问中，把以这个点为根的子树以外的贡献减掉，再遍历这棵树。
当一个点的子树遍历完时，再在树状数组中加上当前点的贡献，并在询问中加上当前所有已遍历部分的贡献。
（这样询问中恰好存有该子树的贡献）

复杂度。
看起来很棒棒啊。
这样可以避免线段树的大常数、大码量和大空间。

定义

然而有一种情况，是以上方法不能处理的。
就是不同子树间的信息相互干扰。

所以考虑把树重链剖分一下。
然后父结点只继承它的重儿子的信息，子树其它部分重新统计。
算完后，如果这个点是其父亲的轻儿子，就把贡献清空，否则不管。
这样也能维护子树信息。
这样复杂度为。

例题

HDU 5709 Claris Loves Painting（离线版本）
求子树中深度不超过的颜色种类数。

考虑一下背景里提到的方法。
,遍历完这棵子树后的答案遍历完这棵子树前的答案这棵子树的答案。

所以老老实实吧。
把询问挂在点上，就按照定义里的方法去搞就行。

有点麻烦的地方是如何维护当前状态下，某种颜色是否存在。
这个吗。。。
拿一个数组维护每种颜色的最浅深度，如果把最浅深度的该颜色点排除了，这种颜色就没了。
为什么可以这样？
因为越浅的点排除越晚。

  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 mk make_pair
  12. #define pb push_back
  13. #define fi first
  14. #define se second
  15. #define fp(i,a,b) for(re int i=a;i<=b;++i)
  16. #define fq(i,a,b) for(re int i=a;i>=b;--i)
  17. using namespace std;
  18. const int N=1e5+100;
  19. int n,m,h[N],cnt,col[N],mn[N],son[N],sz[N],d[N],ans[N],t[N];
  20. vector<pair<int,int> >V[N];
  21. struct Edge{int to,nxt;}e[N<<1];
  22. il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;}
  23. il void Modify(re int x,re int w){for(;x<=n;x+=x&-x) t[x]+=w;}
  24. il int Query(re int x){re int res=0;for(;x;x^=x&-x) res+=t[x];return res;}
  25. il int gi()
  26. {
  27.   re int x=0,t=1;
  28.   re char ch=getchar();
  29.   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  30.   if(ch=='-') t=-1,ch=getchar();
  31.   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  32.   return x*t;
  33. }
  34. il void pre(re int u,re int fa)//找出重儿子
  35. {
  36.   sz[u]=1;d[u]=d[fa]+1;
  37.   for(re int i=h[u];i;i=e[i].nxt)
  38.     {
  39.       re int v=e[i].to;
  40.       pre(v,u);
  41.       sz[u]+=sz[v];
  42.       if(sz[son[u]]<sz[v]) son[u]=v;
  43.     }
  44. }
  45. il void Add(re int x,re int d)//加入新的点，更新颜色最浅深度
  46. {
  47.   if(!mn[x]||mn[x]>d)
  48.     {
  49.       if(mn[x]) Modify(mn[x],-1);
  50.       Modify(mn[x]=d,1);
  51.     }
  52. }
  53. il void clear(re int u)//去除该点，排除该点颜色的影响
  54. {
  55.   if(mn[col[u]]==d[u]) Modify(mn[col[u]],-1),mn[col[u]]=0;
  56.   for(re int i=h[u];i;i=e[i].nxt)
  57.     {
  58.       re int v=e[i].to;
  59.       clear(v);
  60.     }
  61. }
  62. il void upd(re int u)//暴力统计轻儿子子树部分的信息
  63. {
  64.   Add(col[u],d[u]);
  65.   for(re int i=h[u];i;i=e[i].nxt)
  66.     {
  67.       re int v=e[i].to;
  68.       upd(v);
  69.     }
  70. }
  71. il void dfs(re int u,re int tag)
  72. {
  73.   for(re int i=h[u];i;i=e[i].nxt)
  74.     {
  75.       re int v=e[i].to;
  76.       if(v^son[u]) dfs(v,0);
  77.     }//处理轻儿子的答案
  78.   if(son[u]) dfs(son[u],1);//继承重儿子信息
  79.   Add(col[u],d[u]);
  80.   for(re int i=h[u];i;i=e[i].nxt)
  81.     {
  82.       re int v=e[i].to;
  83.       if(v^son[u]) upd(v);
  84.     }//重新统计轻儿子部分信息
  85.   re int sz=V[u].size();
  86.   fp(i,0,sz-1) ans[V[u][i].se]=Query(min(n,d[u]+V[u][i].fi));//回答询问
  87.   if(!tag) clear(u);
  88. }
  89. int main()
  90. {
  91.   n=gi();m=gi();
  92.   fp(i,1,n) col[i]=gi();
  93.   fp(i,2,n)
  94.     {
  95.       re int u=gi(),v=i;
  96.       add(u,v);
  97.     }
  98.   fp(i,1,m)
  99.     {
  100.       re int u=gi(),d=gi();
  101.       V[u].pb(mk(d,i));
  102.     }
  103.   pre(1,1);
  104.   dfs(1,1);
  105.   fp(i,1,m) printf("%d\n",ans[i]);
  106.   return 0;
  107. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注