博客園地址

E：Tree Queries

思路

當我寫完A完這道題后，百度了一下，發現好像沒有人是用類樹鏈剖分來寫的，都是$LCA$，于是我就來水一篇樹鏈剖分題解了。

第一步：貪心取點

我們可以發現，要使所有的點相連我們必須選擇一條最長的路，也就是在$k$個點中，選擇一個與$root=1$最遠的點，這樣才有可能滿足條件，假設起點為$s=1,t=iforiinrange(K)ihavethemax\_dep$

第二步：判斷我們需要查詢的點是否符合條件

我們需要查詢的點，與我們$s?>t$的路徑關系無非就是兩種：一、在這條最短路徑上。二、與路徑相連。

接下來我們就可以通過重鏈的跳轉對這$k$個點判斷是否符合條件了。

對于情況一：我們一定有要滿足$dep[i]<=dep[t]andtop[i]==top[t]$，這樣判斷就有$i$點一定在我們的路徑上。

對于情況二：我們只需要滿足$dep[fa[i]]<=dep[t]+1andtop[fa[i]]==top[t]$，這里可能需要解釋一下$dep[fa]<=dep[t]+1$是怎么來的了，當我們的點直接與$t$相連時，就是這種情況。

第三不：跳躍整條重鏈，到上面一條重鏈上去。

接下來我們跳轉$t$，有$t=fa[top[t]]$，因為我們在上面的操作中已經判斷完了，從$top[t]?>t$上滿足要求的點了，跳轉完后，我們就是再進行步驟二，直到跳躍到點$1$，停止操作，判斷我們最后的答案。

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;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 f * x; }const int N = 2e5 + 10;vector<int> G[N]; int top[N], fa[N], sz[N], dep[N], son[N]; int a[N], visit[N], n, m;void dfs1(int rt, int f) {fa[rt] = f, sz[rt] = 1;dep[rt] = dep[f] + 1;for(int i : G[rt]) {if(i == f) continue;dfs1(i, rt);sz[rt] += sz[i];if(!son[rt] || sz[i] > sz[son[rt]])son[rt] = i;} }void dfs2(int rt, int t) {top[rt] = t;if(!son[rt]) return ;dfs2(son[rt], t);for(int i : G[rt]) {if(i == fa[rt] || i == son[rt]) continue;dfs2(i, i);} }int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);n = read(), m = read();for(int i = 1; i < n; i++) {int x = read(), y = read();G[x].push_back(y);G[y].push_back(x);}dfs1(1, 0);dfs2(1, 1);for(int i = 1; i <= m; i++) {a[0] = read();int max_id = 0, sum = 0;for(int j = 1; j <= a[0]; j++) {visit[j] = 0;a[j] = read();if(dep[a[j]] > dep[max_id]) max_id = a[j];}while(top[max_id] != 1) {for(int j = 1; j <= a[0]; j++)if((top[a[j]] == top[max_id] && dep[a[j]] <= dep[max_id]) || (top[fa[a[j]]] == top[max_id] && dep[a[j]] <= dep[max_id] + 1))if(!visit[j]) {sum++;visit[j] = 1;}max_id = fa[top[max_id]];}for(int j = 1; j <= a[0]; j++)if((top[a[j]] == top[max_id] && dep[a[j]] <= dep[max_id]) || (top[fa[a[j]]] == top[max_id] && dep[a[j]] <= dep[max_id] + 1))if(!visit[j]) {sum++;visit[j] = 1;}puts(sum == a[0] ? "YES" : "NO");}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的E：Tree Queries（假树链剖分写法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。