Submission #113912

#	Time	Username	Problem	Language	Result	Execution time	Memory
113912		MAMBA	Chase (CEOI17_chase)	C++17	0 / 100	311 ms	168424 KiB

chase

    #include <bits/stdc++.h> 
     
    using namespace std;
     
    #define rep(i , j , k) for (int i = j; i < (int)k; i++)
    #define pb push_back
    #define mt make_tuple
    #define all(x) x.begin(),x.end()
     
    typedef long long ll;
    typedef pair<int , int> pii;
    typedef pair<ll, ll> pll;
    typedef long double ld;
    typedef complex<ld> point;
    typedef pair<ld , ld> pld;
    typedef vector<ll> vi;
     
    inline void fileIO(string s) {
    	//	freopen((s + ".in").c_str(), "r", stdin);
    	freopen((s + ".out").c_str(), "w", stdout);
    }
     
    template<class T , class S>
    inline bool smin(T &a, S b) { return (T)b < a ? a = b , 1 : 0; }
    template<class T , class S>
    inline bool smax(T &a, S b) { return a < (T)b ? a = b , 1 : 0; }
     
    constexpr int N = 1e5 + 10;
    constexpr int MOD = 1e9 + 7;
     
    template<typename T>
    inline T mod(T &v) { return v = (v % MOD + MOD) % MOD; }
    template<typename S, typename T>
    inline S add(S &l, T r) { return mod(l += r); }
     
    int n;
    ll dp_up[100][N], dp_down[100][N], v2, p[N], p2[N];
    vi adj[N];
     
    void dfs_down(int v, int par = 0) {
    	dp_down[0][v] = p2[v] - p[v];
    	for (auto e : adj[v]) 
    		if (e ^ par) {
    			dfs_down(e , v);
    			rep(j , 1 , v2)
    				smax(dp_down[j][v] , dp_down[j - 1][e] + p2[v] - 2 * p[v]);
    		}
    }
     
    ll junk[100];
    void dfs_up(int v, int par = 0) {
    	auto f = [v , par]() -> void {
    		rep(i , 0 , v2)
    			junk[i] = dp_up[i][v];
    		for (auto e : adj[v]) 
    			if (e ^ par) {
    				dp_up[0][e] = dp_down[0][e];
    				rep(j , 1 , v2)
    					smax(dp_up[j][e] , junk[j - 1] + p2[e] - 2 * p[e]);
    				rep(j , 0 , v2 - 1) 
    					smax(junk[j + 1] , dp_down[j][e] + p2[v] - 2 * p[v]);
    			}
    	};
    	f();
    	reverse(all(adj[v]));
    	f();
    	for (auto e : adj[v])
    		if (e ^ par)
    			dfs_up(e , v);
    }
     
    int main() {
    	ios::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
     
    	memset(dp_up , -63, sizeof(dp_up));
    	memset(dp_down , -63, sizeof(dp_down));
     
    	cin >> n >> v2;
     
    	if (v2 == 0) return cout << 0 << endl, 0;
     
    	rep(i , 1 , n + 1) {
    		cin >> p[i];
    		p2[i] = p[i];
    	}
    	rep(i , 1 , n) {
    		int u , v;
    		cin >> u >> v;
    		adj[u].pb(v);
    		adj[v].pb(u);
    		p2[u] += p[v];
    		p2[v] += p[u];
    	}
     
    	dfs_down(1);
    	//dp_up[0][1] = dp_down[0][1];
    	//dfs_up(1);
     
      	
      
    	ll res = 0;
    	rep(i , 0 , v2)
   					smax(res , dp_down[i][1]);
          //	rep(j , 1 , n + 1)
    	//	smax(res ,  max(dp_up[i][j] , dp_down[i][j]));
    	
    	cout << res << endl;
     
    	return 0;
    }

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30