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 ;
}