聯合權值——數論

題目來源

洛谷p1351

題目描述

無向連通圖G 有n 個點，n - 1 條邊。點從1 到n 依次編号，編号為 i 的點的權值為W i ，每條邊的長度均為1 。圖上兩點( u , v ) 的距離定義為u 點到v 點的最短距離。對于圖G 上的點對( u, v) ，若它們的距離為2 ，則它們之間會産生Wu×Wv 的聯合權值。

請問圖G 上所有可産生聯合權值的有序點對中，聯合權值最大的是多少？所有聯合權值之和是多少？

輸入輸出格式

輸入格式：

輸入檔案名為link .in。

第一行包含1 個整數n 。

接下來n - 1 行，每行包含 2 個用空格隔開的正整數u 、v ，表示編号為 u 和編号為v 的點之間有邊相連。

最後1 行，包含 n 個正整數，每兩個正整數之間用一個空格隔開，其中第 i 個整數表示圖G 上編号為i 的點的權值為W i 。

輸出格式：

輸出檔案名為link .out 。

輸出共1 行，包含2 個整數，之間用一個空格隔開，依次為圖G 上聯合權值的最大值

和所有聯合權值之和。由于所有聯合權值之和可能很大，輸出它時要對10007 取餘。

輸入輸出樣例

輸入樣例#1：

5

1 2

2 3

3 4

4 5

1 5 2 3 10

輸出樣例#1：

20 74

說明

本例輸入的圖如上所示，距離為2 的有序點對有( 1,3) 、( 2,4) 、( 3,1) 、( 3,5) 、( 4,2) 、( 5,3) 。

其聯合權值分别為2 、15、2 、20、15、20。其中最大的是20，總和為74。

【資料說明】

對于30% 的資料，1 < n≤ 100 ；

對于60% 的資料，1 < n≤ 2000；

對于100%的資料，1 < n≤ 200 , 000 ，0 < wi≤ 10, 000 。

解題思路

• 觀察樣例說明，可以發現每相隔兩個距離的點會正，反各計算兩次。由于權值計算符合乘法交換律，那麼可以隻按照其中的一種順序計算後結果乘二
• 由于兩個間隔距離為二的點會産生聯合權值，而這兩個點相對于其中間的那一個點都間隔一個距離。是以我們可以枚舉中間點。使與中間點相連的所有節點兩兩組合。
• 對于每個中間點，枚舉所有與他相連的點，将該點與已經周遊過的點的權值和相乘。然後将該點放入已周遊過的點的序列中。這樣所得到的結果就是對每一個聯合權值隻按照一種順序計算所得到的結果。
• 求最大的聯合權值可以先求出每一個中間點的最大聯合權值後從中找出最大值，而每一個點的最大聯合權值是其中權值最大的兩個點的權值之積。
• 注意：本題中的最大值不需要取模，僅權值之和需要取模
• -

源代碼

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
struct set;
long long ans = ;
int head[];
int dis[];
int i = ;
int n;
long long MAX = -;
long long data[];
struct edge {
    int next;
    int to;
} edge[];
void add(int from,int to) {
    edge[++i].next = head[from];
    edge[i].to = to;
    head[from] = i;
}
int main() {
    freopen("in.txt","r",stdin);
    cin >> n ;
    int u,v;
    for(int i = ; i < n; i++) {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i = ; i <= n; i++){
        scanf("%d",&data[i]);
        data[i] = data[i] % ;
    }
    for(int i = ;i <= n;i++){
        long long sum = ;
        long long MAX1 = -,MAX2 = -;
        for(int j = head[i];j != ;j = edge[j].next){
            if(data[edge[j].to] > MAX1){ // 計算最大值和次大值
                MAX2 = MAX1;
                MAX1 = data[edge[j].to];
            }else if(data[edge[j].to] > MAX2)
                MAX2 = data[edge[j].to];
            ans = (ans + sum * data[edge[j].to]) % ; // 講該點與已經周遊過的點的權值和相乘
            sum = (sum + data[edge[j].to]) % ; //計算已經周遊過的點的權值和
            MAX = max(MAX,MAX1 * MAX2); // 對比目前中間點的最大權值與之前所得到的最大權值
        }
    }
    cout << MAX << " " << (ans * ) % ;//結果為目前計算值二倍
}