题解 P4175 【[CTSC2008]网络管理】

一万年了。 小蒟蒻Jf终于更博啦>_< 感觉自己已经彻底变成一个鸽子了呢qwq。 ———————————————以上是闲话————————————————————————— ## 这里提供一个树分块的题解。 其时间复杂度为(m+n) sqrt (n) 空间复杂度为n sqrt (n) **前置芝士**： O1lca(这个挺基础的吧) 值域分块（可以参考[小蒟蒻之前的blog](https://www.luogu.org/blog/Juan-feng/solution-p3834)） 那么废话不多说， 直接开始讲实现方法。 在树上选出T个关键点（选取的方法和性质后面会说）， 在把这些关键点之间的LCA也设成关键点，然后将值域分块，处理出这些关键点到根的路径中的一些信息： > cnt1（i, j）表示第i个关键点到根的路径中， 权值在第j个值域块中的点的数量 > cnt2（i, j) 表示第i个关键点到根的路径中， 权值为j的点的数量 显然上面的两个数组可以在T * n 的时间内处理完成。 然后关于这T个点的选取， 我们想让其拥有这样的性质： 从树上的任何一个点出发向根跳最多跳T*(常数）次就可以跳到一个关键点。 显然可以通过贪心来选取这T个点， 然后小Jf比较懒， 就随机了T个点， 据某毒瘤说复杂度也是正确的qwq。（贪心的具体方法本文不进行具体介绍， 可以参考2015年邹逍遥的国家集训队论文） 有了上面的性质， 问题就简单了。 我们先对树进行染色。 将树上向根上跳**第一个**遇到的**关键点相同**的**点** 染上相同的颜色。 那么对于询问x，y，k。 如果xy的颜色**相同**， 那么显然可以在O（T）的实现内暴力进行查询（记录下路径上经过的点用值域分块进行查询）。 对于颜色**不同**的x，y， 我们可以进行如下的讨论：  情况1: 如上图，记x的颜色为xx， y的颜色为yy， xx和yy并非祖先-后代关系。 这种情况是最简单的， 直接处理一下散块（x到xx， y到yy)的信息（蓝色） 然后xx到yy的信息（红色） 可以通过**xx到根的信息** + **yy到根的信息** - **2*lca(xx, yy)到根的信息** 来得到。 然后值域分块来求k大就可以了。  情况2：如上图，记x的颜色为xx， y的颜色为yy, xx和yy是祖先=后代关系， **且**lca（x,y） 是xx,yy中的一个点的祖先， 同时是其中另外一个点的后代。 这种情况下， 如果我们和之前一样处理散块（x到xx，y到yy）的信息（蓝色）和xx到yy的信息（红色）的话， 就会发现多处理了图上<红蓝色>的部分, 而且多处理了两次。 这个时候我们只需要在处理散块信息的时候特殊处理一下就行了。 恩。 那么查询就讲完了qwq 其实修改也很简单， 直接判断一下所有关键点到根的路径中是否经过修改的点， 如果经过的话就在处理的信息中单次O1进行修改就可以了>_< (注意这里需要O1查询的lca， 不然复杂度带log）效率为O（T） 当T取sqrt(n)时， 算法的时间复杂度为(n+m)sqrt(n) 空间复杂度为n sqrt(n) 貌似就没有什么啦qwq 有什么问题的话欢迎来私信小蒟蒻啊qwqwq **那么代码如下：** ``` #include <iostream> #include <cstring> #include <cmath> #include <cstdio> #include <algorithm> #include <ctime> #define maxn 400010 #define maxs 330 #define re register #define FOR(i, l, r) for(re int i = l; i <= r; ++i) #define DFR(i, l, r) for(re int i = l; i >= r; --i) using namespace std; int n, m, c, r, t, x, y, k, tot; int sq1, sq2, num, cnt, col, theone, fh, lastans; int a[maxn], b[maxn], depth[maxn], cnt1[maxs*2][maxs], cnt2[maxs*2][maxn]; int qwq[maxn], san1[maxn], san2[maxn], dis[maxn], head[maxn], numb[maxn]; int fa[maxn], near[maxn], z[maxn], z1[maxn], q[maxn][3]; int f[maxn][20], lg[maxn], id[maxn], vis[maxn], Depth[maxn]; struct hz { int next; int to; }h[maxn*2]; inline int read(){ int x=0;int f=1;char c=getchar(); while(c<'0'||c>'9'){ if(c==-1) return 0; if(c=='-')f=-1; c=getchar(); } while(c<='9'&&c>='0'){ x=(x<<1)+(x<<3)+(c^'0'); c=getchar(); } return x*f; } inline void add(int from, int to) { h[++num].next = head[from]; h[num].to = to; head[from] = num; } void dfs(int x, int ff, int dep) { fa[x] = ff; id[x] = ++tot; depth[x] = depth[ff]+1; vis[tot] = x; Depth[tot] = dep; for(re int i = head[x]; i != 0; i = h[i].next) { if(h[i].to == ff) continue; dfs(h[i].to, x, dep+1); vis[++tot] = x; Depth[tot] = dep; } } void RMQ() { FOR(i, 1, tot) lg[i] = lg[i-1]+(1 << lg[i-1] == i); FOR(i, 1, tot) f[i][0] = i; for(int i = 1; (1<<i) <= tot; i++) { for(int j = 1; j+(1 << i)-1 <= tot; j++) { int A = f[j][i-1]; int B = f[j+(1 << (i-1))][i-1]; if(Depth[A] <= Depth[B]) f[j][i] = A; else f[j][i] = B; } } } int lca(int x, int y) { int r = id[x]; int l = id[y]; if(r < l) swap(r, l); int k = lg[r-l+1]-1; int A = f[l][k]; int B = f[r-(1<<k)+1][k]; if(Depth[A] <= Depth[B]) return vis[A]; else return vis[B]; } void dfs3(int x, int color) { //染色 if(numb[x] != 0) color = numb[x]; near[x] = color; //属于什么管辖范围 for(re int i = head[x]; i != 0; i = h[i].next) { if(h[i].to == fa[x]) continue; dfs3(h[i].to, color); } } inline void deal(int x, int times) { while(x != 0) { ++cnt1[times][b[a[x]]]; ++cnt2[times][a[x]]; x = fa[x]; } } int query(int x, int y, int k) { //求k大 //xy在一个颜色块里, 则直接暴力跳到lca //xy不在一个颜色块里， 且一部分路径重复计算-> 经过lca后转化加减法 if(near[x] == near[y]) { int lc = lca(x, y), xx = x, yy = y, anss = 0; while(x != lc) ++san1[b[a[x]]], ++san2[a[x]], x = fa[x]; while(y != fa[lc]) ++san1[b[a[y]]], ++san2[a[y]], y = fa[y]; int tot = 0, now = 1; while(tot+san1[now] < k) tot += san1[now], ++now; FOR(j, (now-1)*sq1+1, now*sq1) if((tot += san2[j]) >= k) { anss = z[j]; break; } while(xx != lc) --san1[b[a[xx]]], --san2[a[xx]], xx = fa[xx]; while(yy != fa[lc]) --san1[b[a[yy]]], --san2[a[yy]], yy = fa[yy]; return anss; } int lc = lca(x, y), LC = lca(z1[near[x]], z1[near[y]]), xx = x, yy = y; theone = -1, fh = 1; if(lca(z1[near[x]], z1[near[y]]) == LC && (lca(lc, z1[near[x]]) == lc || lca(lc, z1[near[y]])) && lc != LC) { //需要转化加减答案 theone = lc; san1[b[a[LC]]]--, san2[a[LC]]--; } while(near[fa[xx]] == near[x]) { if(xx == theone) { fh *= -1; } else { san1[b[a[xx]]] += fh, san2[a[xx]] += fh; } if(xx == 0) exit(0); xx = fa[xx]; } fh = 1; while(near[fa[yy]] == near[y]) { if(yy == theone) { fh *= -1; yy = fa[yy]; continue; } san1[b[a[yy]]] += fh, san2[a[yy]] += fh, yy = fa[yy]; } ++san1[b[a[LC]]]; ++san2[a[LC]]; int tot = 0, now = 1, anss = 0; while(tot+san1[now]+cnt1[near[x]][now]+cnt1[near[y]][now]-2*cnt1[numb[LC]][now] < k) tot += san1[now]+cnt1[near[x]][now]+cnt1[near[y]][now]-2*cnt1[numb[LC]][now], ++now; FOR(j, (now-1)*sq1+1, now*sq1) if((tot += san2[j]+cnt2[near[x]][j]+cnt2[near[y]][j]-2*cnt2[numb[LC]][j]) >= k) { anss = z[j]; break; } fh = -1, xx = x, yy = y; while(near[fa[xx]] == near[x]) { if(xx == theone) { fh *= -1; xx = fa[xx]; continue; } san1[b[a[xx]]] += fh, san2[a[xx]] += fh, xx = fa[xx]; } fh = -1; while(near[fa[yy]] == near[y]) { if(yy == theone) { fh *= -1; yy = fa[yy]; continue; } san1[b[a[yy]]] += fh, san2[a[yy]] += fh, yy = fa[yy]; } --san1[b[a[LC]]]; --san2[a[LC]]; if(lca(z1[near[x]], z1[near[y]]) == LC && (lca(lc, z1[near[x]]) == lc || lca(lc, z1[near[y]])) && lc != LC) { //需要转化加减答案 san1[b[a[LC]]]++, san2[a[LC]]++; } return anss; } signed main() { srand(19260817); srand(rand()); srand(rand()); n = read(), m = read(); FOR(i, 1, n) { a[i] = read(), z[++z[0]] = a[i]; qwq[i] = i; } FOR(i, 1, n-1) { x = read(), y = read(); add(x, y); add(y, x); } dfs(1, 0, 1); RMQ(); FOR(i, 1, m) { q[i][0] = read(), q[i][1] = read(), q[i][2] = read(); if(q[i][0] == 0) z[++z[0]] = q[i][2]; } sort(z+1, z+z[0]+1); z[0] = unique(z+1, z+z[0]+1)-z-1; FOR(i, 1, n) a[i] = lower_bound(z+1, z+z[0]+1, a[i])-z; sq1 = sqrt(z[0]); //值域分块 FOR(i, 1, z[0]) b[i] = (i-1)/sq1+1; random_shuffle(qwq+1, qwq+n+1); //选取前sq个点 sq2 = sqrt(n); //关键点的数量 FOR(i, 1, sq2) z1[++z1[0]] = qwq[i]; FOR(i, 1, sq2) FOR(j, i+1, sq2) z1[++z1[0]] = lca(qwq[i], qwq[j]); sort(z1+1, z1+z1[0]+1); //关键点排序并去重 z1[0] = unique(z1+1, z1+z1[0]+1)-z1-1; FOR(i, 1, z1[0]) numb[z1[i]] = i; //关键点的新序号 dfs3(1, -2); //染色 FOR(i, 1, z1[0]) //枚举所有新关键点(sq个) 进行处理； deal(z1[i], i); FOR(i, 1, m) { k = q[i][0], x = q[i][1], y = q[i][2]; int sizz = depth[x]+depth[y]-2*depth[lca(x, y)]+1; if(k == 0) { y = lower_bound(z+1, z+z[0]+1, q[i][2])-z; FOR(j, 1, z1[0]) { if(lca(z1[j], x) != x) continue; --cnt1[j][b[a[x]]]; --cnt2[j][a[x]]; ++cnt1[j][b[y]]; ++cnt2[j][y]; } a[x] = y; continue; } if(sizz < k) { puts("invalid request!"); continue; } printf("%d\n", query(x, y, sizz-k+1)); } } ```