xay loves trees

題意：

有兩棵樹，現在讓你找到一個最大的點集合S，要求S中的點在第一棵樹中任意兩點存在祖先兒子關系且所有點是連接的，在第二棵樹中任意兩點都不存在祖先兒子關系，問S集合的最大是多少？

題解：

這個題和CF1528C Trees of Tranquillity這個題差不多，CF這個題沒有對S在第一棵樹中是連續的這個限制。
說下做法：在第二棵樹中任意兩點不存在祖先兒子關系，1號是根節點，我們跑一邊歐拉序，每個點都有一個區間，如果u是v的祖先，那么u的區間一定是覆蓋v的區間的，所以如果集合S中點在第二棵樹中都不是祖先兒子關系，說明他們的區間不會相交。這其實就相當于是個判斷區間相加和加入區間的問題，如果點x的區間與S中的所有區間不沖突，那么x就可以加入到s中。區間問題可以用set或者線段樹實現
再看第一棵樹，要求都是祖先兒子關系且相連，說明就是一個鏈，那我們就直接從第一棵樹的1號節點(根節點)開始dfs，順著找，按照第二棵樹中區間范圍的要求來維護S
比如：下面這個樣例（如圖），dfs第一棵樹，從1開始，此時維護一個set S，判斷1點的區間是否與S中的區間發生沖突，一開始S為空，所以沒沖突，就插入1，然后dfs到點2，看2是否與1沖突，由圖二不難看出，區間1與區間2發生沖突(點1的區間包含了點2)，就彈出1，加入2，差不多就是這個過程。

5 2 1 2 5 5 3 2 4 2 1 1 5 1 3 3 4

但是這里要說的更詳細些，因為我就是沒寫好wa了
dfs過程中，set S是存的目前在集合內的區間情況(用于判斷待加入區間是否相交)，deque d是存當前集合S中有哪些點，stack sta是存被S刪除的點。
看下圖，第一棵樹dfs，從1開始，1的區間不沖突，加入1，然后看2，2的區間與1沖突，刪除1，并用sta保存1，加入2，然后加入3(3的區間與S不沖突)，加入4時，發現沖突，此時我們將S中的按照進入的順序一次彈出，先彈出2，判斷是否沖突，如果沖突再彈出3，否則加入4.
要按照順序依次彈出并判斷，因為S中的沖突是某個區間造成的，比如這里面4是與2沖突的，刪去2，就可以加入4，之后還能加入5，如果先刪3，最佳答案就會受影響(注意題目要求S中的點是連通的)。而sta的存在相當于是給S一個返回操作，在dfs結束后，相當于一個撤回操作，因為dfs每次是搜一個分支，有可能下一個分支更優，所以要回到在搜索分支前的狀態，所有sta要存被刪去的點。
更詳細請看代碼

代碼：

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<set> #include<bits/stdc++.h> using namespace std; inline int read(){int x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();return x; } clock_t startTime, endTime; void rd_test(){#ifdef ONLINE_JUDGE#elsestartTime = clock(); //計時開始freopen("in.txt","r",stdin);#endif } void Time_test(){#ifdef ONLINE_JUDGE#elseendTime = clock(); //計時結束printf("\n運行時間為:%lfs\n",(double)(endTime - startTime) / CLOCKS_PER_SEC);#endif } const int maxn=3e5+10; struct Edge{ int to,next;}edge[maxn*4]; int h1[maxn],h2[maxn],cnt; inline void addedge1(int u,int v){edge[++cnt].to=v,edge[cnt].next=h1[u],h1[u]=cnt; } inline void addedge2(int u,int v){edge[++cnt].to=v,edge[cnt].next=h2[u],h2[u]=cnt; } int n,st[maxn],ed[maxn],idx; void dfs2(int x,int fr){st[x]=++idx;for(int i=h2[x];i;i=edge[i].next){int y=edge[i].to;if(y==fr) continue;dfs2(y,x);}ed[x]=++idx; } set<pair<int,int> > s;inline int check(int id){if(s.size()==0)return 0;set<pair<int,int> >::iterator it=s.lower_bound(make_pair(st[id],id));//大于等于 if(it==s.end()){if(ed[(--it)->second]<st[id])return 0;return 1;}if(it==s.begin()){if(ed[id]<st[it->second])return 0;return 1;}if(ed[id]<st[it->second]&&st[id]>ed[(--it)->second])return 0;return 1; } int ans; deque<int>d; void dfs1(int x,int fr){stack<int> sta;while (check(x)) {sta.push(d.front());d.pop_front();s.erase({st[sta.top()], sta.top()});}s.insert({st[x], x});d.push_back(x);ans=max(ans, (int)s.size());for(int i=h1[x];i;i=edge[i].next){int y=edge[i].to;if(y==fr) continue;dfs1(y,x);}s.erase({st[x], x});d.pop_back();while (!sta.empty()) {d.push_front(sta.top());s.insert({st[sta.top()], sta.top()});sta.pop();} } void solve(){s.clear();for(int i=1;i<=n;i++) h1[i]=h2[i]=0; cnt=0;n=read();for(int i=2;i<=n;i++){int fa=read(),x=read();addedge1(fa,x),addedge1(x,fa);}for(int i=2;i<=n;i++){int fa=read(),x=read();addedge2(fa,x),addedge2(x,fa);}idx=0; dfs2(1,0);ans=0; dfs1(1,0);printf("%d\n",ans); } int main(){//rd_test();int T=read();while(T--) solve();return 0; } /* 1 6 1 1 1 1 2 1 2 1 2 2 */

總結

以上是生活随笔為你收集整理的xay loves trees的全部內容，希望文章能夠幫你解決所遇到的問題。

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