首页 > 代码库 > HDU5331 : Simple Problem
HDU5331 : Simple Problem
因为是二分图，所以最大独立集$=$总点数$-$最大匹配。
因为是树，所以具有贪心性质，设$f_i$表示$i$是否与其孩子匹配，$a_i$表示$i$的孩子里$f$为$0$的个数，则$f_i=[a_i>0]$。
加入一个新的叶子的时候，影响的$a$是连续的一段，这一段上与它距离为奇数的点的$a$都要是$0$，距离为偶数的点都要是$1$。
树链剖分+线段树维护即可。
时间复杂度$O(n\log^2n)$。
#include<cstdio>const int N=100010,M=262150;int n,i,y,f[N],g[N],nxt[N],d[N],size[N],son[N],loc[N],top[N],q[N],dfn;int len[M],v[M],mx[M][2],tag[M][2],rev[M];inline void read(int&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}void dfs(int x){ size[x]=1; for(int i=g[x];i;i=nxt[i]){ d[i]=d[x]+1; dfs(i),size[x]+=size[i]; if(size[i]>size[son[x]])son[x]=i; }}void dfs2(int x,int y){ q[loc[x]=++dfn]=x;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=g[x];i;i=nxt[i])if(i!=son[x])dfs2(i,i);}inline int max(int a,int b){return a>b?a:b;}inline void tag1(int o,int x,int p){mx[x][o]+=p;tag[x][o]+=p;}inline void rev1(int x){v[x]=len[x]-v[x];rev[x]^=1;}inline void pb(int x){ for(int o=0;o<2;o++)if(tag[x][o])tag1(o,x<<1,tag[x][o]),tag1(o,x<<1|1,tag[x][o]),tag[x][o]=0; if(rev[x])rev1(x<<1),rev1(x<<1|1),rev[x]=0;}inline void up(int x){ v[x]=v[x<<1]+v[x<<1|1]; for(int o=0;o<2;o++)mx[x][o]=max(mx[x<<1][o],mx[x<<1|1][o]);}void build(int x,int a,int b){ len[x]=b-a+1;v[x]=rev[x]=0; for(int o=0;o<2;o++)mx[x][o]=tag[x][o]=0; if(a==b)return; int mid=(a+b)>>1; build(x<<1,a,mid),build(x<<1|1,mid+1,b);}void ask(int x,int a,int b,int c,int d,int o){ if(c<=a&&b<=d){ if(mx[x][o]<=1&&mx[x][o^1]<=0){y=a;return;} if(a==b){if(!y)y=N;return;} } pb(x); int mid=(a+b)>>1; if(d>mid){ ask(x<<1|1,mid+1,b,c,d,o); if(y>mid+1)return; } if(c<=mid)ask(x<<1,a,mid,c,d,o);}void change(int x,int a,int b,int c,int d,int o){ if(c<=a&&b<=d){tag1(o,x,-1);tag1(o^1,x,1);return;} pb(x); int mid=(a+b)>>1; if(c<=mid)change(x<<1,a,mid,c,d,o); if(d>mid)change(x<<1|1,mid+1,b,c,d,o); up(x);}void reverse(int x,int a,int b,int c,int d){ if(c<=a&&b<=d){rev1(x);return;} pb(x); int mid=(a+b)>>1; if(c<=mid)reverse(x<<1,a,mid,c,d); if(d>mid)reverse(x<<1|1,mid+1,b,c,d); up(x);}inline void modify(int x,int o){ for(;x;x=f[top[x]]){ y=0; ask(1,1,n,loc[top[x]],loc[x],o); if(y<N)y=q[y]; if(y==N){ change(1,1,n,loc[x],loc[x],o); return; } change(1,1,n,loc[y],loc[x],o); reverse(1,1,n,loc[y],loc[x]); if(y!=top[x]){ y=f[y]; change(1,1,n,loc[y],loc[y],o); return; } }}int main(){ while(~scanf("%d",&n)){ for(dfn=0,i=1;i<=n;i++)g[i]=son[i]=0; for(i=2;i<=n;i++){ read(f[i]),f[i]++; nxt[i]=g[f[i]],g[f[i]]=i; } dfs(1),dfs2(1,1),build(1,1,n); for(i=2;i<=n;i++)modify(f[i],d[i]&1),printf("%d\n",i-v[1]); } return 0;}
HDU5331 : Simple Problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。