CF-1528-C/1529-E Trees of Tranquillity

• 思维难度：提高+/省选-
• 实现难度：提高+/省选-
• 推荐指数：8.0（推荐指数最高为10.0）

题目翻译

Trees of Tranquillity

Soroush and Keshi each have a labeled and rooted tree on $n$ vertices. Both of their trees are rooted from vertex $1$ .

Soroush 和 Keshi 都有一个做了标记的有着 $n$ 个节点的有根树。这两颗树都以节点 $1$ 为根。

Soroush and Keshi used to be at war. After endless decades of fighting, they finally became allies to prepare a Codeforces round. To celebrate this fortunate event, they decided to make a memorial graph on $n$ vertices.

Soroush 和 Keshi 曾经进行过激烈的竞争。在竞争的最后时期，他们成为了同盟来一起准备 Codeforces 比赛。为了庆祝这个幸运时刻，他们决定制作一个有 $n$ 个节点的纪念图。

They add an edge between vertices $u$ and $v$ in the memorial graph if both of the following conditions hold:

• One of $u$ or $v$ is the ancestor of the other in Soroush's tree.
• Neither of $u$ or $v$ is the ancestor of the other in Keshi's tree.

• 在 Soroush 的树上 $u$ 是 $v$ 的祖先或者 $v$ 是 $u$ 的祖先。
• 在 Keshi 的树上 $u$ 和 $v$ 都不是对方的祖先。

Here vertex $u$ is considered ancestor of vertex $v$, if $u$ lies on the path from $1$ (the root) to the $v$.

Popping out of nowhere, Mashtali tried to find the maximum clique in the memorial graph for no reason. He failed because the graph was too big.

Help Mashtali by finding the size of the maximum clique in the memorial graph.

As a reminder, clique is a subset of vertices of the graph, each two of which are connected by an edge.

题解

void dfs(int i)
{
in[i]=++dfn;
dfni[dfn]=i;
for(int p=V[i].eh;p;p=E[p].next)
{
dfs_kt(E[p].to);
}
out[i]=dfn;
}


#pragma GCC optimize ("O2")

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define MAXN 300005
#define lc nodes[i].ch[0]
#define rc nodes[i].ch[1]

struct treap{
struct node{
int v;
int rnd;
int ch[2];
int siz;
}nodes[MAXN*2];
int tot=0,root=0;

void init()
{
tot=0;
root=0;
}

void pushup(int i)
{
nodes[i].siz=nodes[lc].siz+nodes[rc].siz+1;
}

int new_node(int v)
{
int i=++tot;
nodes[i].v=v;
nodes[i].rnd=rand();
nodes[i].siz=1;
lc=rc=0;
return i;
}

void split(int i,int v,int& x,int& y)
{
if(!i) x=y=0;
else
{
if(nodes[i].v<=v) split(rc,v,rc,y),x=i;
else split(lc,v,x,lc),y=i;
pushup(i);
}
}

int merge(int x,int y)
{
if(!x||!y) return x+y;
int i;
if(nodes[x].rnd>nodes[y].rnd)
{
i=x;
rc=merge(rc,y);
}
else
{
i=y;
lc=merge(x,lc);
}
pushup(i);
return i;
}

void insert(int v)
{
int x,y;
split(root,v,x,y);
root=merge(merge(x,new_node(v)),y);
}

void remove(int v)
{
int i,x,y;
split(root,v,x,y);
split(x,v-1,x,i);
i=merge(lc,rc);
root=merge(merge(x,i),y);
}

int find_pre(int v)
{
int x,y,i,ans;
split(root,v-1,x,y);
i=x;
while(rc) i=rc;
ans=nodes[i].v;
root=merge(x,y);
return ans;
}

int find_next(int v)
{
int x,y,i,ans;
split(root,v,x,y);
i=y;
while(lc) i=lc;
ans=nodes[i].v;
root=merge(x,y);
return ans;
}

int size()
{
return nodes[root].siz;
}
}t;

struct tree{
struct node{
int eh;
}V[MAXN];

struct edge{
int to;
int next;
}E[MAXN];

int tot;

{
E[++tot]=(edge){to,V[from].eh};
V[from].eh=tot;
}

void init(int n)
{
tot=0;
memset(V+1,0,sizeof(node)*n);
//注意这里不能初始化整个数组，不然会超时
}
}st,kt;

int in[MAXN],out[MAXN];
int dfn;
int dfni[MAXN];

void dfs_kt(int i)
{
auto& E=kt.E;
auto& V=kt.V;
in[i]=++dfn;
dfni[dfn]=i;
for(int p=V[i].eh;p;p=E[p].next)
{
dfs_kt(E[p].to);
}
out[i]=dfn;
}

int ans;

void dfs_st(int i)
{
auto& E=st.E;
auto& V=st.V;

int j=dfni[t.find_next(in[i])],tmp=0;
bool flag=false;

if(!(j&&out[i]>=out[j]))
{
flag=true;
t.insert(in[i]);
j=dfni[t.find_pre(in[i])];
if(j&&out[j]>=out[i])
{
tmp=in[j];
t.remove(in[j]);
}
}

if(t.size()>ans) ans=t.size();

for(int p=V[i].eh;p;p=E[p].next)
{
dfs_st(E[p].to);
}

if(flag) t.remove(in[i]);
if(tmp) t.insert(tmp);
}

int main()
{
srand((unsigned)time(NULL));
int T,n,i,tmp;
scanf("%d",&T);
while(T--)
{
//initialize
scanf("%d",&n);
st.init(n);
kt.init(n);
t.init();
dfn=0;
ans=0;

//input
for(i=2;i<=n;i++)
{
scanf("%d",&tmp);
}
for(i=2;i<=n;i++)
{
scanf("%d",&tmp);
}

//solve
dfs_kt(1);
dfs_st(1);

//output
printf("%d\n",ans);
}
return 0;
}


标签

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.