xay loves trees

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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。