P6071 『MdOI R1』Treequery
<h2 id="p6071-mdoi-r1treequery">P6071 『MdOI R1』Treequery</h2><p>简单分讨题。</p>
<p>若 <span class="math inline">\(\)</span> 内的点全部在 <span class="math inline">\(p\)</span> 子树内：</p>
<ul>
<li>考虑找到 <span class="math inline">\(q = \operatorname{LCA}(l, l + 1, \cdots, r - 1, r)\)</span>，显然 <span class="math inline">\(q\)</span> 也在 <span class="math inline">\(p\)</span> 子树内，那么答案为 <span class="math inline">\(\operatorname{dis}(p, q) = dep_q - dep_p\)</span>。</li>
</ul>
<p>若 <span class="math inline">\(\)</span> 内的点一部分在 <span class="math inline">\(p\)</span> 子树内，一部分在外面：</p>
<ul>
<li>显然，此时答案为 <span class="math inline">\(0\)</span>。</li>
</ul>
<p>否则若 <span class="math inline">\(\)</span> 内的点全部都在 <span class="math inline">\(p\)</span> 子树外：</p>
<ul>
<li>
<p>显然我们先应该找到 <span class="math inline">\(q \in , \operatorname{LCA}(p, q)\)</span> 中深度最深的那个点 <span class="math inline">\(q\)</span>。</p>
</li>
<li>
<p>转化一下，即我们只用找到一个点 <span class="math inline">\(q\)</span>，满足 <span class="math inline">\(q\)</span> 是 <span class="math inline">\(p\)</span> 祖先且 <span class="math inline">\(q\)</span> 子树内包含 <span class="math inline">\(\)</span> 中其中一个点即可且是满足这些条件中最深的，可以倍增暴力跳然后判断。</p>
</li>
<li>
<p>然后需要继续特判：若 <span class="math inline">\(q\)</span> 子树内包含了所有的 <span class="math inline">\(\)</span>，那么令 <span class="math inline">\(R = \operatorname{LCA}(l, l + 1, \cdots, r - 1, r)\)</span>，故 <span class="math inline">\(R\)</span> 肯定在 <span class="math inline">\(q\)</span> 子树内，答案为 <span class="math inline">\(\operatorname{dis}(p, R) = dep_p + dep_R - 2dep_q\)</span>。否则只有一部分在 <span class="math inline">\(p\)</span> 子树内，其它的在外面，则答案为 <span class="math inline">\(\operatorname{dis}(p, q) = dep_p - dep_q\)</span>。</p>
</li>
</ul>
<p>然后说一下如何判断 <span class="math inline">\(p\)</span> 子树内有多少个点在 <span class="math inline">\(\)</span> 范围内，考虑差分为 <span class="math inline">\( - \)</span>，然后只需要考虑前缀；考虑使用主席树，即 <span class="math inline">\(T_i\)</span> 维护了编号为 <span class="math inline">\(\)</span> 的点的时间戳序列，<span class="math inline">\(T_i \to T_{i + 1}\)</span> 只需要单点修改 <span class="math inline">\(dfn_{i + 1}\)</span> 即可；查询则在 <span class="math inline">\(T_r\)</span> 与 <span class="math inline">\(T_{l - 1}\)</span> 查询区间 <span class="math inline">\(\)</span> 和即可。</p>
<p>哦，还有个查询区间 <span class="math inline">\(\operatorname{LCA}\)</span>，可以转化为相邻 <span class="math inline">\(\operatorname{LCA}\)</span> 中深度最小的那个，那么使用 ST 表即可做到单 <span class="math inline">\(\log\)</span>。</p>
<p>套上倍增，时间复杂度为 <span class="math inline">\(O(N \log^2 N)\)</span>，空间复杂度为 <span class="math inline">\(O(N \log N)\)</span>。</p>
<p><strong>link</strong></p>
<h3 id="完整代码">完整代码：</h3>
<pre><code class="language-cpp">#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 10, M = 20;
inline ll read(){
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
inline void write(ll x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
ll d;
int n, q, u, v, w, p, l, r, ans, cnt;
int dfn, siz, dep, top, son, lg, fa, rt, Fa;
pair<int, int> F;
vector<pair<int, int>> E;
inline void add(int u, int v, int w){
E.push_back({v, w});
E.push_back({u, w});
}
namespace Seg{
int node;
struct Node{
int lson, rson;
int sum;
}X;
inline void newnode(int &k){
X[++node] = X;
k = node;
}
inline void update(int &k, int l, int r, int i){
newnode(k);
++X.sum;
if(l == i && i == r)
return ;
int mid = (l + r) >> 1;
if(i <= mid)
update(X.lson, l, mid, i);
else
update(X.rson, mid + 1, r, i);
}
inline int ask(int k, int l, int r, int ql, int qr){
if(!k)
return 0;
if(l == ql && qr == r)
return X.sum;
int mid = (l + r) >> 1;
if(qr <= mid)
return ask(X.lson, l, mid, ql, qr);
else if(ql > mid)
return ask(X.rson, mid + 1, r, ql, qr);
else
return ask(X.lson, l, mid, ql, mid) + ask(X.rson, mid + 1, r, mid + 1, qr);
}
};
inline void dfs1(int u, int f){
for(int i = 1; i < M; ++i)
Fa = Fa];
siz = 1;
for(auto t : E){
int v = t.fi, w = t.se;
if(v == f)
continue;
d = d + w;
dep = dep + 1;
fa = Fa = u;
dfs1(v, u);
siz += siz;
if(siz > siz])
son = v;
}
}
inline void dfs2(int u, int k){
dfn = ++cnt;
top = k;
if(!son)
return ;
dfs2(son, k);
for(auto t : E){
int v = t.fi;
if(v == fa || v == son)
continue;
dfs2(v, v);
}
}
inline int lca(int u, int v){
while(top != top){
if(dep] < dep])
swap(u, v);
u = fa];
}
return dep < dep ? u : v;
}
inline int LCA(int l, int r){
if(l == r)
return l;
--r;
int k = lg;
return min(F, F).se;
}
inline int ASK(int u, int l, int r){
return Seg::ask(rt, 1, n, dfn, dfn + siz - 1) - Seg::ask(rt, 1, n, dfn, dfn + siz - 1);
}
int main(){
// freopen("A.in", "r", stdin);
// freopen("A.out", "w", stdout);
lg = -1;
n = read(), q = read();
for(int i = 1; i < n; ++i){
lg = lg + 1;
u = read(), v = read(), w = read();
add(u, v, w);
}
dfs1(1, 1);
dfs2(1, 1);
for(int i = 1; i <= n; ++i){
rt = rt;
Seg::update(rt, 1, n, dfn);
}
for(int i = 1; i < n; ++i){
u = lca(i, i + 1);
F = {dep, u};
}
for(int j = 1; j < M; ++j)
for(int i = 1; i + (1 << j) <= n; ++i)
F = min(F, F);
while(q--){
p = read() ^ ans, l = read() ^ ans, r = read() ^ ans;
int now = ASK(p, l, r), all = LCA(l, r);
if(now == r - l + 1)
ans = d - d;
else if(!now){
int q = p;
for(int i = M - 1; i >= 0; --i)
if(Fa && !ASK(Fa, l, r))
q = Fa;
q = fa;
now = ASK(q, l, r);
if(now == r - l + 1)
ans = d + d - (d << 1ll);
else
ans = d - d;
}
else
ans = 0;
write(ans);
putchar('\n');
}
return 0;
}
</code></pre><br><br>
来源：https://www.cnblogs.com/rgw2010/p/18924089
頁:
[1]