【点分树】codechef Yet Another Tree Problem

已经连咕了好几天博客了；比较经典的题目

题目大意

给出一个 N 个点的树和$K_i$，求每个点到其他所有点距离中第 $K_i$ 小的数值。

题目分析

做法一：点分树上$log^3$

首先暴力做法：对于每个节点维护其他点距离的值域线段树。这个做法的瓶颈在于关于边$(u,v)$线段树的转移。那么可以利用点分树（为了保证复杂度）换一种容斥的思路利用重复的信息：记$f_i$为以$i$为根的点分树内所有其他点到点$i$的距离的值域线段树；$g_i$为以$i$为根的点分树内，所有点到$i$的点分树父亲的距离的值域线段树。

询问的时候，记$LIM$为二分的长度，查询点为$pos$，$lst$的点分树父亲为$i$，那么每一层的贡献就是$f_i$中$LIM-dis(pos,i)$减去$g_{lst}$中$LIM-dis(pos,i)$的代价，注意还要特判一下$(pos,i)$这条路径是否会被算入贡献。

  1 #include<bits/stdc++.h>
  2 const int maxLog = 20;
  3 const int maxn = 100035;
  4 const int maxm = 200035;
  5 const int maxNode = 20000035;
  6 
  7 struct node
  8 {
  9     int l,r,val;
 10 };
 11 int LIM;
 12 struct RangeSeg
 13 {
 14     int tot,rt[maxn];
 15     node a[maxNode];
 16     void modify(int &rt, int l, int r, int pos)
 17     {
 18         if (!rt) rt = ++tot;
 19         ++a[rt].val;
 20         if (l==r) return;
 21         int mid = (l+r)>>1;
 22         if (pos <= mid) modify(a[rt].l, l, mid, pos);
 23         else modify(a[rt].r, mid+1, r, pos);
 24     }
 25     int query(int rt, int L, int R, int l, int r)
 26     {
 27         if (!rt) return 0;
 28         if (L <= l&&r <= R) return a[rt].val;
 29         int mid = (l+r)>>1, ret = 0;
 30         if (L <= mid) ret = query(a[rt].l, L, R, l, mid);
 31         if (R > mid) ret += query(a[rt].r, L, R, mid+1, r);
 32         return ret;
 33     }
 34     void modify(int x, int c)
 35     {
 36         modify(rt[x], 1, LIM, c);
 37     }
 38     int query(int x, int l, int r)
 39     {
 40         if (l <= r) return query(rt[x], l, r, 1, LIM);
 41         else return 0;
 42     }
 43 }f,g;
 44 int n,k[maxn];
 45 int dep[maxn],fat[maxn][maxLog],lay[maxn];
 46 int size[maxn],bloTot,son[maxn],root;
 47 int edgeTot,head[maxn],nxt[maxm],edges[maxm];
 48 bool vis[maxn];
 49 
 50 int read()
 51 {
 52     char ch = getchar();
 53     int num = 0, fl = 1;
 54     for (; !isdigit(ch); ch=getchar())
 55         if (ch=='-') fl = -1;
 56     for (; isdigit(ch); ch=getchar())
 57         num = (num<<1)+(num<<3)+ch-48;
 58     return num*fl;
 59 }
 60 void addedge(int u, int v)
 61 {
 62     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
 63     edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
 64 }
 65 int lca(int x, int y)
 66 {
 67     if (dep[x] > dep[y]) std::swap(x, y);
 68     for (int i=17; i>=0; i--)
 69         if (dep[fat[y][i]] >= dep[x]) y = fat[y][i];
 70     if (x==y) return x;
 71     for (int i=17; i>=0; i--)
 72         if (fat[x][i]!=fat[y][i]) x = fat[x][i], y = fat[y][i];
 73     return fat[x][0];
 74 }
 75 int dist(int x, int y){return dep[x]+dep[y]-(dep[lca(x, y)]<<1);}
 76 void dfs(int x, int fa)
 77 {
 78     fat[x][0] = fa, dep[x] = dep[fa]+1;
 79     for (int i=1; i<=17; i++)
 80         fat[x][i] = fat[fat[x][i-1]][i-1];
 81     for (int i=head[x]; i!=-1; i=nxt[i])
 82         if (edges[i]!=fa) dfs(edges[i], x);
 83 }
 84 void getRoot(int x, int fa)
 85 {
 86     size[x] = 1, son[x] = 0;
 87     for (int i=head[x]; i!=-1; i=nxt[i])
 88     {
 89         int v = edges[i];
 90         if (v==fa||vis[v]) continue;
 91         getRoot(v, x);
 92         size[x] += size[v];
 93         son[x] = std::max(son[x], size[v]);
 94     }
 95     son[x] = std::max(son[x], bloTot-size[x]);
 96     if (son[x] < son[root]) root = x;
 97 }
 98 void color(int Top, int x, int fa)
 99 {
100     if (Top!=x) f.modify(Top, dist(Top, x));
101     if (lay[Top]) g.modify(Top, dist(lay[Top], x));
102     for (int i=head[x]; i!=-1; i=nxt[i])
103         if (edges[i]!=fa&&!vis[edges[i]]) color(Top, edges[i], x);
104 }
105 void deal(int x, int pre)
106 {
107     lay[x] = pre, color(x, x, x), vis[x] = true;
108     for (int i=head[x]; i!=-1; i=nxt[i])
109     {
110         int v = edges[i];
111         if (vis[v]) continue;
112         bloTot = size[v], root = 0, getRoot(v, 0);
113         deal(root, x);
114     }
115 }
116 int count(int x, int num)
117 {
118     int ret = f.query(x, 1, num);
119     for (int i=lay[x],lst=x; i; lst=i,i=lay[i])
120     {
121         int d = dist(x, i);
122         if (d <= num) ++ret, ret += f.query(i, 1, num-d)-g.query(lst, 1, num-d);
123     }
124     return ret;
125 }
126 int main()
127 {
128     memset(head, -1, sizeof head);
129     LIM = n = read();
130     for (int i=1; i<=n; i++) k[i] = n-read();
131     for (int i=1; i<n; i++) addedge(read(), read());
132     dfs(1, 0);
133     bloTot = n, root = 0, son[0] = n, getRoot(1, 0);
134     deal(root, 0);
135     for (int i=1; i<=n; i++)
136     {
137         int L = 0, R = LIM, ans = 0;
138         for (int mid=(L+R)>>1; L<=R; mid=(L+R)>>1)
139             if (count(i, mid) < k[i]) L = mid+1, ans = mid;
140             else R = mid-1;
141         printf("%d ",ans);
142     }
143     return 0;
144 }

做法二：序列问题分块

不说了。类似的套路见#6046. 「雅礼集训 2017 Day8」爷