首页 > 代码库 > BZOJ 2466: [中山市选2009]树

BZOJ 2466: [中山市选2009]树

Sol

树形DP.

听说有非常神奇的高斯消元的做法...orz...

然而我只会 \(O(n)\) 的树形DP.

首先一个点的状态只于他的父节点和子树有关,跟他 子树的子树 和 父亲的父亲 都没有任何关系.

这样就可以DP了.

\(f[i][0/1][0/1]\) 表示\(i\)节点,点了 \(0/1\) 次,状态是 \(0/1\) (暗或亮).

然后就瞎转移就可以了,具体看代码吧.

Code

/**************************************************************    Problem: 2466    User: BeiYu    Language: C++    Result: Accepted    Time:4 ms    Memory:1292 kb****************************************************************/ #include<cstdio>#include<vector>#include<cstring>#include<iostream>using namespace std; const int N = 105;const int INF = 0x03ffffff; int n;int f[N][2][2];vector<int> g[N]; inline int in(int x=0,char ch=getchar()){ while(ch>‘9‘||ch<‘0‘) ch=getchar();    while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar();return x; } void DP(int u,int fa){//  if(fa&&g[u].size()==1){ f[u][0][0]=0,f[u][0][1]=INF,f[u][1][0]=INF,f[u][1][1]=1;return; }    int t0=0,t1=INF,t2=INF,t3=0;    for(int i=0,lim=g[u].size(),v;i<lim;i++) if((v=g[u][i])!=fa){        DP(v,u);        int s0=t0,s1=t1,s2=t2,s3=t3;        t0=min(s1+f[v][1][1],s0+f[v][0][1]);        t1=min(s1+f[v][0][1],s0+f[v][1][1]);        t2=min(s3+f[v][1][0],s2+f[v][0][0]);        t3=min(s3+f[v][0][0],s2+f[v][1][0]);    }    f[u][0][0]=t0,f[u][0][1]=t1;    f[u][1][0]=t2+1,f[u][1][1]=t3+1;}int main(){//  freopen("in.in","r",stdin);    for(;n=in();){        for(int i=1;i<N;i++) g[i].clear();        for(int i=1,u,v;i<n;i++) u=in(),v=in(),g[u].push_back(v),g[v].push_back(u);        DP((n+1)/2,0);        cout<<min(f[(n+1)/2][1][1],f[(n+1)/2][0][1])<<endl;//      DP(1,0);//      cout<<min(f[1][1][1],f[1][0][1])<<endl;//      for(int i=1;i<=n;i++)//          cout<<i<<"->"<<f[i][0][0]<<" "<<f[i][0][1]<<" "<<f[i][1][0]<<" "<<f[i][1][1]<<endl;//      cout<<"*******************"<<endl;    }return 0;}

  

BZOJ 2466: [中山市选2009]树