POJ 3140 树形DP

题目

Contestants Division

Time Limit: 2000MS Memory Limit: 65536K

Total Submissions: 9191 Accepted: 2634

Description

In the new ACM-ICPC Regional Contest, a special monitoring and submitting system will be set up, and students will be able to compete at their own universities. However there’s one problem. Due to the high cost of the new judging system, the organizing committee can only afford to set the system up such that there will be only one way to transfer information from one university to another without passing the same university twice. The contestants will be divided into two connected regions, and the difference between the total numbers of students from two regions should be minimized. Can you help the juries to find the minimum difference?

Input

There are multiple test cases in the input file. Each test case starts with two integers N and M, (1 ≤ N ≤ 100000, 1 ≤ M ≤ 1000000), the number of universities and the number of direct communication line set up by the committee, respectively. Universities are numbered from 1 to N. The next line has N integers, the Kth integer is equal to the number of students in university numbered K. The number of students in any university does not exceed 100000000. Each of the following M lines has two integers s, t, and describes a communication line connecting university s and university t. All communication lines of this new system are bidirectional.

N = 0, M = 0 indicates the end of input and should not be processed by your program.

Output

For every test case, output one integer, the minimum absolute difference of students between two regions in the format as indicated in the sample output.

Sample Input

7 6

1 1 1 1 1 1 1

1 2

2 7

3 7

4 6

6 2

5 7

0 0

Sample Output

Case 1: 1

题意

给你一课树，删除一条边，新成两颗树。求两颗树之差的绝对值最小的情况。

题解

很容易就想到dp[i]为第i个节点的所有子节点的和，总和是已知的，那么两者之差就出来了。接着枚举切断的边求最小值就可以了。

在树的具体实现上，我们要是能明确知道一个节点的儿子节点和父亲节点就能方便后来的合并操作。用son，brother，father这三个数组来表示这个树。然后bfs确定出相应数组的值。接着dfs就可以求出dp所有的的值来了。

注意。这个答案可能非常大，ans初始化要为0x7ffffffffffffll。没注意这个点导致wa了一次。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <string>
#include <set>
#include <cmath>
#include <map>
#include <queue>
#include <sstream>
#include <vector>
#include <iomanip>
#define m0(a) memset(a,0,sizeof(a))
#define mm(a) memset(a,0x3f,sizeof(a))
#define m_1(a) memset(a,-1,sizeof(a))
#define f(i,a,b) for(i = a;i<=b;i++)
#define fi(i,a,b) for(i = a;i>=b;i--)
#define lowbit(a) ((a)&(-a))
#define FFR freopen("data.in","r",stdin)
#define FFW freopen("data.out","w",stdout)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
const ld PI = acos(-);

using namespace std;
#define SIZE ( 100000+11)

struct Po {
    int x, y;
};

bool cmp(const Po& a, const Po& b) {
    if (a.x < b.x)
        return true;
    else if (a.x == b.x)
        return a.y < b.y;
    return false;
}

ll a[SIZE];
Po G[SIZE*];
int b[SIZE*];
int father[SIZE];
int brother[SIZE];
int son[SIZE];
ll dp[SIZE];
ll sum;

void bfs(int root) {
    m0(father); m0(brother); m0(son);
    queue<int>qu;
    qu.push(root);
    while (!qu.empty()) {
        root = qu.front(); qu.pop();
        int v = b[root];
        while (G[v].x==root) {
            if (father[root] != G[v].y) {
                father[G[v].y] = root;
                brother[G[v].y] = son[root];
                son[root] = G[v].y;
                qu.push(G[v].y);
            }
            v++;
        }
    }
}

void dfs(int root) {
    dp[root] = a[root];
    int v = son[root];
    while (v) {
        dfs(v);
        dp[root] += dp[v];
        v = brother[v];
    }
}

ll Abs(ll k) {
    if (k < )
        return (-L)*k;
    return k;
}

int main() {
    //ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m;
    int CNT = ;
    while (~scanf("%d%d",&n,&m)&&(n||m) ) {
        int i, j;
        sum = ;
        f(i, , n)
        {
            scanf("%I64d", &(a[i]));
            sum += a[i];
        }
        j = ;
        f(i, , m) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (x != y) {
                G[++j].x = x; G[j].y = y;
                G[++j].x = y; G[j].y = x;
            }
        }

        sort(G + , G +  + j, cmp);

        m0(b);
        f(i, , j)
            if (!b[G[i].x])
                b[G[i].x] = i;

        bfs();
        m0(dp);
        dfs();
        ll ans = ll;
        f(i, , n)
            if (Abs(dp[i] - (sum - dp[i])) < ans)
                ans = Abs(dp[i] - (sum - dp[i]));
        printf("Case %d: %I64d\n", CNT++, ans);
    }
    return ;
}