题解 P5024 【保卫王国】

pipiispig · 2019-11-04 15:01:01 · 题解

震惊(ΩДΩ)，本题光会最简单的树形dp就可以得到84分的高分，学什么ddp, 要立起旗帜，反对毒瘤！

因为题解中吗没有讲部份分的，所以我就发一个84分的纯暴力吧， 可以提供一下骗分思路，懒得讲了，自己看吧（我觉得代码难度很低）

subtask0 对应44分的O(NM)暴力

subtask1 对应1号特性

subtask2 对应2号特性

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 10;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return f * x;
}
int ver[N << 1], nexts[N << 1], head[N], e = 1;
inline void add(int x, int y) {
    ver[++ e] = y;
    nexts[e] = head[x];
    head[x] = e;
}
string s;
int n, m, dep[N], a[N];
ll dp[N][2];
ll up[N][2];
void dfs(int x, int fa) {
    for(int i = head[x]; i; i = nexts[i]) {
        int v = ver[i];
        if(v == fa) continue;
        dep[v] = dep[x] +1;
        dfs(v, x);
        dp[x][1] += min(dp[v][1], dp[v][0]);
        dp[x][0] += dp[v][1];
    }
    dp[x][1] += a[x];
}
void dfs2(int x, int fa) {
    for(int i = head[x]; i; i = nexts[i]) {
        int v = ver[i];
        if(v == fa) continue;
        up[v][0] = up[x][1] + dp[x][1] - min(dp[v][0], dp[v][1]);
        up[v][1] = min(up[v][0], up[x][0] + dp[x][0] - dp[v][1]);
        dfs2(v, x);
    }
}
inline void subtask0() {
    for(int i = 1; i <= m; i ++) {
        int x = read(), a1 = read(), y = read(), b1 = read();
        memset(dp, 0, sizeof(dp));
        dp[y][!b1] = dp[x][!a1] = 0x3f3f3f3f3f3f3f3f;
        dfs(1, 0);
        if(dp[1][0] >= 0x3f3f3f3f3f3f3f3f && dp[1][1] >= 0x3f3f3f3f3f3f3f3f) puts("-1");
        else printf("%lld\n", min(dp[1][0], dp[1][1]));
    }
}
inline void subtask1() {
    up[1][0] = dp[1][0] = 0x3f3f3f3f3f3f3f3f;
    dfs(1, 0); dfs2(1, 0);
    for(int i = 1; i <= m; i ++) {
        int x = read(), a1 = read(), y = read(), b1 = read();
        printf("%lld\n", dp[y][b1] + up[y][b1]);
    }
}
inline void subtask2() {
    dfs(1, 0); dfs2(1, 0);
    for(int i = 1; i <= m; i ++) {
        int x = read(), a1 = read(), y = read(), b1 = read();
        if(a1 == 0 && b1 == 0) {puts("-1"); continue;}
        if(dep[x] < dep[y]) swap(x, y), swap(a1, b1);
        printf("%lld\n", dp[x][a1] + up[y][b1] + (b1 == 1 ? dp[y][1] - min(dp[x][0], dp[x][1]) : dp[y][0] - dp[x][1]));
    }
}
int main() {
    n = read(), m = read();
    cin >> s;
    for(int i = 1; i <= n; i ++) 
        a[i] = read();
    for(int i = 1; i < n; i ++) {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    if(n <= 2000 && m <= 2000) subtask0();
    else if(s[1] == '1') subtask1();
    else if(s[1] == '2') subtask2();
    else printf("hack, please!");
    return 0;
}