解题思路

算法设计

采用树形动态规划方法解决最大权子树问题。

核心思想

• 将树视为有根树进行遍历
• 每个节点维护两个状态值
• 通过子树信息合并求解全局最优解

实现步骤

1. 任选一个节点作为根节点
2. 后序遍历整棵树
3. 对每个节点计算两个状态值
4. 根节点的dp[root][0]即为最终答案

复杂度分析

• 时间复杂度：O(N)，每个节点仅被处理一次
• 空间复杂度：O(N)，存储树结构和状态值

算法特点

• 适用于平面整点树（每个节点最多4个邻居）
• 通过选择性合并正权子树优化结果
• 后序遍历确保子问题先被解决

/*
    PROG: POJ1192
    PROB:
*/
 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
 
#define DEBUG 1
#define LOG(...) do { if (DEBUG) fprintf(stderr, __VA_ARGS__); } while(0)
 
#define MAXN 1005
int M[MAXN][MAXN];
char vis[MAXN][MAXN];
int N, val[MAXN];
 
struct Point {
    int x, y;
    Point(int x=0, int y=0) : x(x), y(y) {}
};
 
typedef vector<Point> VP;
typedef pair<int, int> PII;
 
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
 
 
PII wk(int x, int y) {
    PII ret(-10000000, -10000000);
    vis[x][y] = 1;
    int curr = val[M[x][y]];
    for (int dir = 0; dir < 4; ++dir) {
        int tx = x+dx[dir], ty = y+dy[dir];
        if (tx<0||ty<0||tx>=MAXN||ty>=MAXN) continue;
        if (vis[tx][ty]||M[tx][ty]<0) continue;
        PII tmp(wk(tx,ty));
        ret.first = max(ret.first, tmp.first);
        if (tmp.second>0) curr += tmp.second;
    }
    ret.second = curr;
    ret.first = max(ret.first, ret.second);
    vis[x][y] = 0;
    return ret;
}
 
int main(void) {
    scanf("%d", &N);
    VP pts(N);
    int x, y, mx, my; scanf("%d%d%d", &mx, &my, val);
    pts[0] = Point(mx, my);
    for (int i = 1; i < N; ++i) {
        scanf("%d%d%d", &x, &y, val+i);
        pts[i] = Point(x, y);
        mx = min(mx, x);
        my = min(my, y);
    }
    memset(M, -1, sizeof(M));
    // LOG("%d, %d\n", mx, my);
    for (int i = 0; i < N; ++i) {
        pts[i].x -= mx, pts[i].y -= my;
        M[pts[i].x][pts[i].y] = i;
        // LOG("%d %d\n", pts[i].x, pts[i].y);
    }
    PII ans = wk(pts[0].x, pts[0].y);
    printf("%d\n", ans.first);
    return 0;
}