題意：https://ac.nowcoder.com/acm/contest/11258/F 給出兩樹S1， S2， 求一個點集，滿足這個點集上的點都在S1上的一條鏈上（且聯通），并且在S2中，這個點集任意兩點沒有祖先關系，
首先， 我們可以先預處理S2， 求出S2中每個點的dfs序，并記錄這個點及其的后代的dfs序的范圍，這樣一來，每個點的dfs 序就都是一個連續的區間，且該點的后代的dfs序區間包含在它的祖先的區間里，這樣操作的好處在于如果兩個節點沒有祖先關系，那他們的dfs序的區間就不會互相包含，
接下來，我們可以 dfs S1，對每條鏈進行處理，注意到在S1中， 這個集合的點是相連的， 那么也就是說這些點在一條鏈上的位置是相鄰的，然后要找出的是這個區間長度的最大值，由于我說不清楚，我們可以想到用滑動視窗來處理，只要能夠判斷出新進的點能夠滿足與視窗里的點沒有互相包含的區間，那么這個區間的右端就可以延申下去，否則，我們就得將視窗的左端慢慢移到右端，并進行判斷，直到滿足條件，即為一個合理的區間，
那么問題來了，怎么判斷呢？ 我們可以想到， 當一個區間出現過時，我們可以將這個區間里所有數都加1，并維護起來，當dfs到另一個點時， 我們也對這個新進的點的區間里所有數加1，然后查詢這個區間和，如果這個區間和剛好等于區間長度，那么這個區間就是沒被包含過也沒包含過其他區間，否則，視窗的左端就得左移，并對移出來的點的區間減1，直到剛剛處理的新進來的點的區間和等于其區間長度，然后維護區間最大值，
這里要注意， 在每走一步的回溯時，我們要把視窗和維護區間的資料結構還原到這個新進的點沒處理前的樣子，這一步結合代碼應該很好理解，
對于區間修改， 區間查詢我們可以用線段樹，樹狀陣列等資料結構實作，下面的代碼給出的是一個樹狀陣列的方法，
理論復雜度 nlogn
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define pb push_back
#define endl '\n'
using namespace std;
using ll = long long;
const int maxn = 3e5 + 10;
vector <int> tree1[maxn], tree2[maxn];
int L[maxn], R[maxn];//第二顆樹的dfs序的范圍
//樹狀陣列維護區間和
int tree[maxn];
int sum[maxn];
//
int kk;
int ans = 0;
void dfs(int num, int last) //求dfs序
{
L[num] = ++kk;
for (int i : tree2[num])
{
if (i == last) continue;
dfs(i, num);
}
R[num] = kk;
}
int lef = 0, rig = -1, n;
int p[maxn];
//樹狀陣列處理程序
void update(int id, int val)
{
int y = id;
while (id < n + 2)
{
tree[id] += val;
sum[id] += val * y;
id += (id & (-id));
}
}
int query(int num)
{
int a = 0, y = num;
while (num > 0)
{
a += (y + 1) * tree[num] - sum[num];
num -= (num & (-num));
}
return a;
}
//對第一棵樹的每一條鏈進行滑動視窗處理
void dfs1(int num, int last)
{
int l = lef, r = rig;
p[++rig] = num;
update(L[num], 1);
update(R[num] + 1, -1);
while (query(R[num]) - query(L[num] - 1) > R[num] - L[num] + 1)
{
int t = p[lef];
update(L[t], -1);
update(R[t] + 1, 1);
lef++;
}
ans = max(ans, rig - lef + 1);
for (int i : tree1[num])
{
if (i == last) continue;
dfs1(i, num);
}
//還原到該點沒有處理前的樣子
update(L[num], -1);
update(R[num] + 1, 1);
rig--;
while (lef > l)
{
lef--;
update(L[p[lef]], 1);
update(R[p[lef]] + 1, -1);
}
}
void solve()
{
int i, j, u, v;
cin >> n;
lef = 0, rig = -1;
kk = 0; ans = 0;
for (i = 1; i <= n; i++) tree1[i].clear(), tree2[i].clear();
memset(tree, 0, sizeof(int) * (n + 10));
memset(sum, 0, sizeof(int) * (n + 10));
memset(L, 0, sizeof(int) * (n + 10));
memset(R, 0, sizeof(int) * (n + 10));
for (i = 1; i < n; i++)
{
cin >> u >> v;
tree1[u].pb(v);
tree1[v].pb(u);
}
for (i = 1; i < n; i++)
{
cin >> u >> v;
tree2[u].pb(v);
tree2[v].pb(u);
}
dfs(1, -1);
dfs1(1, -1);
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
/*
1
5
2 1
2 5
5 3
2 4
2 1
1 5
1 3
3 4
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/292716.html
標籤：其他
上一篇：【計算機網路】搞定DNS協議入門