CF 1529E. Trees of Tranquillity

文章目錄

• • 題意：
  • 題解：
  • 代碼：
  • • 線段樹代碼：
    • 利用set實現

題意：

有A1，A2兩棵樹，根是1，編號都是1~n，先制作圖A3，如果兩個點的x和y同時滿足以下兩個條件則連邊，
1.在樹A中x是y的祖先或者y是x的祖先
2.在樹B中x和y誰都不是誰的祖先
求A3的最大的團集的大小
團：圖G的一個完全子圖
題目A1和A2的輸入方式為：
a2，a3…an, ai是樹的頂點i的父親節點(1<= ai <i)

題解：

參考題解：
文章1
文章2
我們需要將題意轉化：
滿足最大團的點是什么樣的？團要求任意兩點都有連線，也就是最大團中所有點同時滿足題目說的兩個條件，因此這些點在A樹上是一條的(沒有分支)。在B樹上體現為彼此不是父親節點，我們引入dfs序，發現所有點的dfs序沒有交集。
對于本題的輸入還有一個特殊性質：ai <i，說明A樹和B樹從根節點出發的鏈，一定是一個單調遞增的序列。針對B樹的dfs序區間，就會有：序號較小的點的區間，要么包含序號較大的點的區間，要么與其不相交
對于兩個點的dfs序區間，要么沒有交集(不是父子關系)，要么存在包含(父子關系)，且左端點與右端點是對應的，父親系節點的區間包含兒子節點的區間，因此對于一個互相包含的區間，我們要保留較小的(這樣才能存下更多不相交的區間)，對應到樹上，相當于 當一個點的兒孫可選時該點不選最優
現在我們從第一棵樹的根開始dfs，每到一個點就往某數據結構中加入自己的區間：
1.如果被數據結構中原先的更大區間包含，那就刪除大區間，加入小區間
2.如果包含了原有的至少一個小區間，那就不加
3.否則就加進去，答案+1
回溯時，數據結構要退回原來的狀態

這個某數據結構可以用set，線段樹等等
線段樹具體實現過程：
先求樹2的dfs序，然后對樹1從根節點開始，查看當前點u的區間內是否有區間，如果沒有直接插入，如果有，一定是比自己大的區間，所以刪除原大區間，加入新區間。記錄當前答案最大值，對u的兒子繼續查找。回溯時逆向操作

代碼：

線段樹代碼：

代碼里有注釋

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; vector<int>a[N],b[N]; int L[N],R[N],dfn,sum,ans; struct Node {int l,r,mmax,lazy; }tree[N<<2]; void pushup(int k) {tree[k].mmax=max(tree[k<<1].mmax,tree[k<<1|1].mmax); } void pushdown(int k) {if(tree[k].lazy!=-1) {int lz=tree[k].lazy;tree[k].lazy=-1;tree[k<<1].mmax=tree[k<<1|1].mmax=lz;tree[k<<1].lazy=tree[k<<1|1].lazy=lz;} } void build(int k,int l,int r) {tree[k]={l,r,0,-1};if(l==r) {return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void update(int k,int l,int r,int val) {if(tree[k].l>r||tree[k].r<l) {return;}if(tree[k].l>=l&&tree[k].r<=r) {tree[k].mmax=tree[k].lazy=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); } int query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].mmax;}pushdown(k);return max(query(k<<1,l,r),query(k<<1|1,l,r)); } void dfs1(int u) {//求樹2的dfs序 L[u]=++dfn;for(auto v:b[u]) {dfs1(v);}R[u]=dfn; } void dfs2(int u) {int mmax=query(1,L[u],R[u]);if(!mmax) {//如果沒有區間 update(1,L[u],R[u],u);sum++;} else {//存在區間，且區間一定比自己大 update(1,L[mmax],R[mmax],0);//刪除原本區間 update(1,L[u],R[u],u);//加入新區間 }ans=max(ans,sum);for(auto v:a[u]) {dfs2(v);//對u的兒子節點繼續查找 }//回溯操作 if(!mmax) {update(1,L[u],R[u],0);sum--;} else {update(1,L[u],R[u],0);update(1,L[mmax],R[mmax],mmax);} } int main() {int w;cin>>w;while(w--) {int n;read(n);dfn=0;for(int i=1;i<=n;i++) {a[i].clear();b[i].clear();}for(int i=2;i<=n;i++) {int fa;read(fa);a[fa].push_back(i);}for(int i=2;i<=n;i++) {int fa;read(fa);b[fa].push_back(i);}dfn=ans=sum=0;build(1,1,n);dfs1(1);dfs2(1);cout<<ans<<endl;}return 0; }

利用set實現

#include<set> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define MAXN 300005 #define ENDL putchar('\n') #define LL long long #define DB double #define lowbit(x) ((-x) & (x)) #define SI set<int>::iterator LL read() {LL f = 1,x = 0;char s = getchar();while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}return f * x; } int n,m,i,j,s,o,k; vector<int> g0[MAXN]; int L[MAXN],R[MAXN],lR[MAXN],tim;//lR[]數組是為L找到唯一的R void dfs0(int x,int ff) {//求 樹2的dfs序 L[x] = ++ tim;for(int i = 0;i < (int)g0[x].size();i ++) {if(g0[x][i] != ff) dfs0(g0[x][i],x);}R[x] = tim; lR[L[x]] = R[x];return ; } vector<int> g[MAXN]; int d[MAXN],dfn[MAXN],rr[MAXN],cnt,ans; set<int> st; void dfs(int x,int ff) {int ad = 0;if(st.empty()) st.insert(L[x]);//如果此時為空，直接插入 else {SI i = st.lower_bound(L[x]);//查找是否已經有區間 if(i != st.begin()) //發現有區間 {i --;if(lR[*i] >= R[x])//存在更大區間包含 {ad = *i;st.erase(ad);//刪除大區間 st.insert(L[x]);//加入小區間 }else {i ++;if(i == st.end() || *i > R[x]) //里面沒有小區間，加入的區間不會相交 st.insert(L[x]);}}else if(i == st.end() || *i > R[x]) st.insert(L[x]);//發現沒區間 }ans = max(ans,(int)st.size());for(int i = 0;i < (int)g[x].size();i ++) {if(g[x][i] != ff) dfs(g[x][i],x);}//回溯操作 if(st.find(L[x]) != st.end()) st.erase(L[x]);if(ad) st.insert(ad);return ; } int main() {int T = read();while(T --) {n = read();tim = 0; cnt = 0;st.clear();for(int i = 1;i <= n;i ++) {g0[i].clear();g[i].clear();lR[i] = 0;}for(int i = 2;i <= n;i ++) {s = read(); g[s].push_back(i);}for(int i = 2;i <= n;i ++) {s = read(); g0[s].push_back(i);}dfs0(1,0);ans = 0;dfs(1,0);printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的CF 1529E. Trees of Tranquillity的全部內容，希望文章能夠幫你解決所遇到的問題。

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