分块。
Solution
看到是区修区查，还有时限，不难想到是分块，根号复杂度。
然后看到空间复杂度，需要离线下来转为线性复杂度。
考虑如何分块。观察操作性质，发现节点深度越大对答案的贡献就越小，即，若一个点将要跳的祖先已经在区间里出现过了，那它目前就没有意义了。这启发我们实时维护这些“有意义的节点”，每次整块修改的时候只需要跳这些节点即可。
但是散块的修改可能会让曾经“无意义”的节点变为“有意义的”——它可能单独跳很多，这样就变为有意义的了。为了让这些无意义节点还能往上跳祖先，我们还需要维护一个 \(tag\)，表示整块处理了几次，即让当前所有有意义节点一起向上跳父亲跳了几次。不妨思考，一个无意义节点和有意义节点的差别是什么？就是它在变为无意义节点之后，其他有意义节点跳父亲时，它没有参与。那现在我想让它变为有意义节点，只需要把它“错过”的几次跳父亲操作补回来就可以了。所以在 \(tag\) 的基础上，我们对于每个节点 \(i\)，还要维护 \(val_i\)，表示它参与了几次整块处理时所有有意义节点进行的跳父亲操作。那么现在，对于散块中的一个节点，我只需要让它向上跳 \(tag - val_i+1\) 次父亲即可完成修改——其中 \(+1\) 是当前对它的修改，\(tag-val_i\) 是它错过的修改。跳完之后，再看它是否变为有意义节点，如果是，那么把它扔进序列中、打标记，维护即可。
查询的话，因为是离线对每个块单独处理，所以我们可以实时维护整块的答案；对于散块，按照散块修改时的方式让散块的节点单独跳祖先，对于每个节点单独统计贡献即可。
维护/跳祖先的话，直接使用重链剖分即可，不影响复杂度。
总时复 \(\mathcal{\text{O}}(n\sqrt n)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
#define go(u) for(int i = hd[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)
const int maxn = 2e5 + 5;
int n, m, rt;
struct que{
int opt, l, r;
}q[maxn]; ll dep[maxn], ans[maxn];
int cnt, hd[maxn];
struct node{
int to, nxt, w;
}e[maxn << 1];
int fa[maxn], siz[maxn], mxs[maxn];
int dp[maxn], tp[maxn], dfn[maxn], tot, idfn[maxn];
bool vis[maxn], inq[maxn];
int a[maxn], que[maxn], top, val[maxn], tag;
inline void add(int u, int v, int w){
e[++cnt] = (node){v, hd[u], w}; hd[u] = cnt;
}
inline void dfs1(int u, int f){
dp[u] = dp[fa[u] = f] + 1, siz[u] = 1;
go(u) if(v ^ f){
dep[v] = dep[u] + e[i].w, dfs1(v, u);
if(siz[mxs[u]] < siz[v]) mxs[u] = v;
siz[u] += siz[v];
}
}
inline void dfs2(int u, int anc){
tp[u] = anc, dfn[u] = ++tot, idfn[tot] = u;
if(!mxs[u]) return; dfs2(mxs[u], anc);
go(u) if(v != fa[u] and v != mxs[u])
dfs2(v, v);
}
inline int kth(int x, int k){
if(k >= dp[x]) return rt;
while(k >= dp[x] - dp[tp[x]] + 1)
k -= dp[x] - dp[tp[x]] + 1, x = fa[tp[x]];
return idfn[dfn[x] - k];
}
inline void slv(int L, int R){
tag = top = 0; ll anss = 1e18;
rep(i, 1, n) vis[i] = inq[i] = que[i] = val[i] = 0;
rep(i, L, R) if(!vis[a[i]])
que[++top] = i, inq[i] = 1, vis[a[i]] = 1, anss = min(anss, dep[a[i]]);
rep(i, 1, m){ int l = max(L, q[i].l), r = min(R, q[i].r);
if(l > r) continue;
if(q[i].opt == 1)
if(l == L and r == R){ tag += 1; int tmp = top; top = 0;
rep(j, 1, tmp){ val[que[j]] += 1;
if(vis[a[que[j]] = fa[a[que[j]]]]) inq[que[j]] = 0;
else que[++top] = que[j], vis[a[que[j]]] = 1,
anss = min(anss, dep[a[que[j]]]);
}
} else rep(j, l, r){
if(!vis[a[j] = kth(a[j], tag - val[j] + 1)]){
anss = min(anss, dep[a[j]]), vis[a[j]] = 1;
if(!inq[j]) que[++top] = j, inq[j] = 1;
} val[j] = tag;
}
else{ if(l == L and r == R) ans[i] = min(ans[i], anss);
else rep(j, l, r)
ans[i] = min(ans[i], dep[a[j] = kth(a[j], tag - val[j])]), val[j] = tag;
}
}
}
signed main(){ int len;
scanf("%d%d%d", &n, &m, &rt); len = sqrt(n);
rep(i, 2, n){ int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
} dfs1(rt, rt), dfs2(rt, rt);
rep(i, 1, n) scanf("%d", &a[i]);
rep(i, 1, m) ans[i] = 1e18,
scanf("%d%d%d", &q[i].opt, &q[i].l, &q[i].r);
for(int i = 1; i <= n; i += len)
slv(i, min(i + len - 1, n));
rep(i, 1, m) if(q[i].opt == 2) printf("%lld\n", ans[i]);
return 0;
}
感谢阅读。
标签：空复,val,题解,rep,anss,离线,tag,que,节点 From： https://www.cnblogs.com/gsn531/p/16754309.html