傳送門(mén)

文章目錄

• 題意：
• 思路：

題意：

給你兩棵有$n$個(gè)節(jié)點(diǎn)的樹(shù)，我門(mén)記第一棵為$a$，第二棵為$b$，現(xiàn)在你有一個(gè)$n$個(gè)點(diǎn)都孤立的點(diǎn)集，兩個(gè)點(diǎn)$u,v$可以連邊當(dāng)且僅當(dāng)這兩個(gè)點(diǎn)在$a$樹(shù)中一個(gè)是另一個(gè)的祖先節(jié)點(diǎn)且在$b$樹(shù)中每個(gè)都不是另一個(gè)的祖先節(jié)點(diǎn)，讓你求連完邊之后的最大聯(lián)通塊的大小是多少。
兩棵樹(shù)都以$1$為根。
$n\le 3e5$

思路：

首先我們知道答案選的點(diǎn)一定是$a$樹(shù)中從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑上點(diǎn)的一個(gè)子集，這啟發(fā)我們可以從$a$樹(shù)的根開(kāi)始向下$dfs$，維護(hù)走過(guò)的點(diǎn)，現(xiàn)在我們的問(wèn)題就是如何從我們維護(hù)的點(diǎn)中選出一個(gè)最大的點(diǎn)集使其在$b$樹(shù)中都是符合條件的。
在$b$樹(shù)中選出來(lái)的每?jī)蓚€(gè)點(diǎn)都不互為祖先，那么他們倆一定在一棵子樹(shù)內(nèi)，涉及子樹(shù)問(wèn)題我們可以將其轉(zhuǎn)換成$dfs$序。
首先需要了解$dfs$序的性質(zhì)，$dfs$序?qū)⒚總€(gè)子樹(shù)劃分為了若干區(qū)間，也就是每個(gè)子樹(shù)的根有一個(gè)區(qū)間$[l,r]$，且劃分的若干區(qū)間只會(huì)有兩種情況：一個(gè)區(qū)間完全包含另一個(gè)區(qū)間，兩個(gè)區(qū)間完全不相交。
現(xiàn)在我們對(duì)$b$樹(shù)求一個(gè)$dfs$序，現(xiàn)在每個(gè)點(diǎn)都轉(zhuǎn)換成一個(gè)區(qū)間了，對(duì)$a$來(lái)說(shuō)我們只需要需要維護(hù)一個(gè)從根到當(dāng)前點(diǎn)的若干個(gè)不相交線段，可以分以下兩個(gè)情況：
$(1)$如果我們當(dāng)前插入的點(diǎn)$u$的區(qū)間$[l_u,r_u]$包含了之前插入的區(qū)間，那么我們肯定是舍棄這個(gè)點(diǎn)是更優(yōu)的。
$(2)$如果我們當(dāng)前插入的點(diǎn)在前面已經(jīng)有的點(diǎn)的區(qū)間內(nèi)的話，那么肯定是將前面大區(qū)間刪掉，加入當(dāng)前區(qū)間是更優(yōu)的。
以上操作可以用$set$維護(hù)一下$in[u]$，讓后$lowe{r}_{b}ound$找離他最近的點(diǎn)的$in[v]$，判斷一下就好啦，第二種情況同理，只需要讓$it??$即可，具體的看代碼比較好懂。
復(fù)雜度$O(nlogn)$。

$Update：$
由于題目保證了$a_i<i$，那么說(shuō)明標(biāo)號(hào)一定是遞增的，所以不會(huì)出現(xiàn)當(dāng)前區(qū)間是大區(qū)間，之前有小區(qū)間的情況，所以$it==s.end()||?it>out[u]$這個(gè)判斷條件可以直接去掉。

// Problem: E. Trees of Tranquillity // Contest: Codeforces - Codeforces Round #722 (Div. 2) // URL: https://codeforces.com/contest/1529/problem/E // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid (tr[u].l+tr[u].r>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int in[N],out[N],id[N],tot,ans; set<int>s; vector<int>v1[N],v2[N];void dfs2(int u) {in[u]=++tot; id[tot]=u;for(auto x:v2[u]) dfs2(x);out[u]=tot; }void dfs1(int u) {int flag=false;int del=-1;auto it=s.lower_bound(in[u]);if(it==s.end()||*it>out[u]) {if(it!=s.begin()) {it--;if(out[id[*it]]>=in[u]) {del=*it;s.erase(it);}}s.insert(in[u]);flag=true;}ans=max(ans,(int)s.size());for(auto x:v1[u]) dfs1(x);if(flag) {s.erase(in[u]);if(del!=-1) s.insert(del);} }int main() { // ios::sync_with_stdio(false); // cin.tie(0);int _; scanf("%d",&_);while(_--) {scanf("%d",&n);tot=0; s.clear(); ans=0;for(int i=1;i<=n;i++) v1[i].clear(),v2[i].clear();for(int i=2;i<=n;i++) {int x; scanf("%d",&x);v1[x].pb(i);}for(int i=2;i<=n;i++) {int x; scanf("%d",&x);v2[x].pb(i);}dfs2(1); dfs1(1);printf("%d\n",ans);}return 0; } /**/

總結(jié)

以上是生活随笔為你收集整理的CF1528C dfs序+set维护的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。