树形dp入门题，上司的舞会

川长思鸟来 2022-09-03 13:16 12阅读 0赞

遍历根节点，当前节点为u， 一次遍历儿子节点x  
状态转移方程：  
 d p \[ u \] \[ 0 \] + = m a x ( d p \[ x \] \[ 1 \] , d p \[ x \] \[ 0 \] ) d p \[ u \] \[ 1 \] + = d p \[ x \] \[ 0 \] dp\[u\]\[0\]+= max(dp\[x\]\[1\], dp\[x\]\[0\]) \\\\ dp\[u\]\[1\] += dp\[x\]\[0\] dp\[u\]\[0\]\+=max(dp\[x\]\[1\],dp\[x\]\[0\])dp\[u\]\[1\]\+=dp\[x\]\[0\]

// Problem: P1352 没有上司的舞会
    // Contest: Luogu
    // URL: https://www.luogu.com.cn/problem/P1352
    // Memory Limit: 128 MB
    // Time Limit: 1000 ms
    // 
    // Powered by CP Editor (https://cpeditor.org)
    
    #include<iostream>
    #include<cstdio>
    #include<string>
    #include<ctime>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<stack>
    #include<climits>
    #include<queue>
    #include<map>
    #include<set>
    #include<sstream>
    #include<cassert>
    #include<bitset>
    #include<list>
    #include<unordered_map>
    using namespace std;
    #define lowbit(x) (x&-x)
    #define pf(a) printf("%d\n",a)
    #define mem(x,y) memset(x,y,sizeof(x))
    #define dbg(x) cout << #x << " = " << x << endl
    #define rep(i,l,r) for(int i = l; i <= r; i++)
    #define fep(i,a,b) for(int i=b;i>=a;--i)
    typedef long long ll;
    typedef unsigned long long ull;
    
    // const int inf=0x3f3f3f3f;
    const int N=6100;
    vector<int> v[N];
    int a[N],p[N],dp[N][2];
    int n;
    
    void dfs(int u)
    { 
    	dp[u][1] = a[u];
    	for(auto x : v[u])
    	{ 
    		dfs(x);
    		dp[u][1] += dp[x][0];
    		dp[u][0] += max(dp[x][0], dp[x][1]);
    	}
    }
    
    void solve()
    { 
    	cin >> n;
    	rep(i,1,n) cin >> a[i];
    	rep(i,1,n-1)
    	{ 
    		int a, b;
    		cin >> a >> b;
    		p[a] = b;
    		v[b].push_back(a);
    	}
    	int root = 0;
    	rep(i,1,n)
    		if(!p[i]){ 
    			root = i;
    			break;
    		}
    	dfs(root);
    	cout << max(dp[root][0], dp[root][1]) << endl;
    }
    
    int main()
    { 
    
    	ios::sync_with_stdio(false);cin.tie(0);
    	// int Case;cin >> Case;
    	// while(Case--)
    		solve();
    	return 0;
    }