原题见COGS或SYZOJ
联合权值这道题啊，是一道数学题（此处大雾...
我还是有点不能理解这种算法。。明天再细细研究，先把代码贴出来。
对了，%晨耀防止爆零。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <vector> #define LL long long #define Chenyao2333 10007 using namespace std; const int MX = 200005; LL w[MX]; LL maxn, sum, n; bool vis[MX]; vector <int> g[MX]; queue <int> q; int main() { freopen("linkb.in", "r", stdin); freopen("linkb.out", "w", stdout); scanf("%lld", &n); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } for (int i = 1; i <= n; i++) { scanf("%lld", w + i); } q.push(1); vis[1] = 1; while (!q.empty()) { int u = q.front(); q.pop(); LL suma = 0, sumb = 0; LL max1 = 0, max2 = 0; //cout << g[u].size(); for (int i = 0; i < g[u].size(); i++) { int v = g[u][i]; suma = (suma + w[g[u][i]]) % Chenyao2333; sumb = (sumb + (w[v] * w[v] % Chenyao2333)) % Chenyao2333; if (w[v] > max1) { max2 = max1; max1 = w[v]; } else if (w[v] > max2) { max2 = w[v]; } if (!vis[v]) { vis[v] = 1; q.push(v); } } sum = (sum + ((suma * suma) % Chenyao2333 - sumb + Chenyao2333) % Chenyao2333) % Chenyao2333; maxn = max(maxn, max1 * max2); } printf("%lld %lld", maxn, sum); return 0; } |