CF1633F题解
Tyyyyyy
·
·
题解
CF1633F
题意简述
给定一棵 n 个点的树，初始时只有 1 号点被激活。
处理两种操作：
### 题目分析
首先考虑解决树不变时的问题。显然首先要选择与叶子节点直接相连的边，然后隔一条选一条，看是否合法。
如果我们设一个点的状态 $f_u=0/1$，且 $f_u=1$，当且仅当连接 $u$ 和其父节点的边被选择，那么我们对于一个叶子节点的选边就是把它到根的路径上所有的 $f_u$ 取反。
用树剖 + 线段树就可以很方便地维护这个区间取反的过程。我们还要在线段树中记录选择的边数 $cnt$。如果全局 $cnt=\frac{n}{2}$，那么就合法。
然后现在这道题是不断加点，因为新加的点肯定是叶子，所以我们上面的做法可以直接做这道题。至于输出方案，因为不超过 $10$ 次询问所以直接暴力 dfs 就可以了。
Code：
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,tot,h[N];
struct edge
{
int v,w,nxt;
}e[N<<1];
void add(int u,int v,int w)
{
e[++tot]=(edge){v,w,h[u]};
h[u]=tot;
}
int fa[N],siz[N],dep[N],wson[N];
void prework(int u)
{
siz[u]=1;
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u])continue;
fa[v]=u,dep[v]=dep[u]+1;
prework(v),siz[u]+=siz[v];
if(siz[wson[u]]<siz[v])wson[u]=v;
}
}
int dfn[N],id[N],idx,top[N],a[N];
void dfs(int u,int t)
{
top[u]=t,id[dfn[u]=++idx]=u;
if(wson[u])dfs(wson[u],t);
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==wson[u])a[v]=e[i].w;
if(v==fa[u]||v==wson[u])continue;
dfs(v,v),a[v]=e[i].w;
}
}
struct SegmentTree
{
ll sum[N<<2],s[N<<2];
int cnt[N<<2],tag[N<<2];
void pushup(int p){s[p]=s[p<<1]+s[p<<1|1],cnt[p]=cnt[p<<1]+cnt[p<<1|1];}
void adtag(int p,int l,int r)
{
tag[p]^=1,cnt[p]=(r-l+1)-cnt[p],s[p]=sum[p]-s[p];
}
void pushdown(int p,int l,int r)
{
if(!tag[p])return;
int mid=(l+r)>>1;
adtag(p<<1,l,mid),adtag(p<<1|1,mid+1,r);
tag[p]=0;
}
void build(int p,int l,int r)
{
if(l==r){cnt[p]=(l==1),sum[p]=a[id[l]];return;}
int mid=(l+r)>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
pushup(p),sum[p]=sum[p<<1]+sum[p<<1|1];
}
void upd(int p,int l,int r,int L,int R)
{
if(L<=l&&r<=R){adtag(p,l,r);return;}
pushdown(p,l,r);
int mid=(l+r)>>1;
if(L<=mid)upd(p<<1,l,mid,L,R);
if(R>mid)upd(p<<1|1,mid+1,r,L,R);
pushup(p);
}
}segt;
bool act[N],chs[N];
int acnt;
vector<int>way;
void getans(int u)
{
for(int i=h[u];i;i=e[i].nxt)
{
int v=e[i].v;
if(v==fa[u]||!act[v])continue;
getans(v);
if(!chs[v])chs[u]=1,way.push_back(e[i].w);
}
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)
scanf("%d%d",&x,&y),add(x,y,i),add(y,x,i);
prework(1),dfs(1,1),segt.build(1,1,n),act[1]=1,acnt=1;
int op,u;ll ans=0;
while(1)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d",&u);
act[u]=1,acnt++;
while(u)
{
segt.upd(1,1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(segt.cnt[1]*2==acnt)ans=segt.s[1];
else ans=0;
printf("%lld\n",ans),fflush(stdout);
}
else if(op==2)
{
if(ans)
{
way.resize(0),memset(chs,0,sizeof(chs));
getans(1),sort(way.begin(),way.end());
printf("%d ",(int)way.size()),fflush(stdout);
for(int x:way)printf("%d ",x),fflush(stdout);
puts(""),fflush(stdout);
}
else puts("0"),fflush(stdout);
}
else break;
}
return 0;
}
```