题面
solve
今天模拟赛考到一道一模一样的题目,但我还写了1h+,真的是越来越菜了
其实这道题一股树形 \(DP\) 的味道,但是要考虑很多状态,父亲,儿子,兄弟,所以考虑贪心
对于一颗以 \(x\) 为根节点的子树,我们考虑几种情况
-
需要父节点和兄弟节点给一点贡献
-
可以给父节点和兄弟节点一点贡献
-
自洽,给不了父亲和兄弟一点东西
我们实际处理的时候可以不分这三种情况,开 \(should[x]\) 和 \(give[x]\) 表示需要的贡献和能给出的贡献
然后分类讨论一下,看一下需不需要放就好了
显然,越往上面放坑定好,所以能不放就不放,只有非不得已的时候再放
code
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,maxe=2e6+5,INF=0x3f3f3f3f;
int N,ans;
int lnk[maxn],son[maxe],nxt[maxe],fa[maxn],cnt,shod[maxn],giv[maxn];
struct IO{
static const int S=1<<21;
char buf[S],*p1,*p2;int st[105],Top;
~IO(){clear();}
inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='\n'||x=='r');return *this;}
template<typename T>inline IO&operator >> (T&x){
x=0;bool f=0;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
f?x=-x:0;return *this;
}
inline IO&operator << (const char c){pc(c);return *this;}
template<typename T>inline IO&operator << (T x){
if(x<0) pc('-'),x=-x;
do{st[++st[0]]=x%10,x/=10;}while(x);
while(st[0]) pc('0'+st[st[0]--]);return *this;
}
}fin,fout;
inline void add_e(int x,int y){
son[++cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;
}
void push(int x){
giv[x]=2;shod[x]=-INF;
}
inline int max(int x,int y){return x>y?x:y;}
void DFS(int x){
shod[x]=-INF;giv[x]=-INF;
for(int j=lnk[x];j;j=nxt[j])if(son[j]!=fa[x]){
DFS(son[j]);
shod[x]=max(shod[x],shod[son[j]]);
giv[x]=max(giv[x],giv[son[j]]);
}
if(shod[x]==2){
ans++;push(x);return ;
}
if(shod[x]==1){
if(giv[x]>1){shod[x]=-INF;giv[x]--;return ;}
if(giv[x]==1) {giv[x]=-INF;shod[x]++;return ;}
if(giv[x]==-INF) {shod[x]++;return ;}
}
if(shod[x]==-INF){
if(giv[x]==-INF){shod[x]=1;return ;}
if(giv[x]==1){giv[x]=-INF;return ;}
if(giv[x]==2){giv[x]--;return ;}
}
return;
}
int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
fin>>N;
for(int i=1;i<N;i++) {fin>>fa[i+1];add_e(i+1,fa[i+1]);add_e(fa[i+1],i+1);}
DFS(1);if(shod[1]!=-INF)ans++;
fout<<ans<<'\n';
return 0;
}