結果
問題 | No.386 貪欲な領主 |
ユーザー |
|
提出日時 | 2024-10-12 23:45:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,182 bytes |
コンパイル時間 | 1,727 ms |
コンパイル使用メモリ | 171,860 KB |
実行使用メモリ | 25,092 KB |
最終ジャッジ日時 | 2024-10-12 23:45:17 |
合計ジャッジ時間 | 5,082 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 16 |
ソースコード
# include <bits/stdc++.h>using namespace std;typedef long long ll;//# define int long long# define lc u << 1# define rc u << 1 | 1# define fi first# define se secondconst int N = 100005;int n, m, a, b, c;int parent[100000][18];int depth[100000];vector <int> adj[100000];long long int u[100000];int query[200000][3];long long int arr[100000];void dfs(int now){for (auto next : adj[now]){if (depth[next] == -1){parent[next][0] = now;depth[next] = depth[now] + 1;dfs(next);}}}int getlca(int x, int y){if (depth[x] < depth[y]){int t = y;y = x;x = t;}int d = abs(depth[x] - depth[y]);for (int j = 0; d > 0; j++){if (d % 2){x = parent[x][j];}d /= 2;}if (x != y){for (int j = 18 - 1; j >= 0; j--){if (parent[x][j] != -1 && parent[x][j] != parent[y][j]){x = parent[x][j];y = parent[y][j];}}x = parent[x][0];}return x;}void func(int now,int prev,long long int sum){sum += u[now];arr[now] = sum;for (auto next : adj[now]){if (next == prev) continue;func(next, now, sum);}}signed main (){scanf ("%d", &n);for (int i = 0; i < n - 1; i++){cin >> a >> b;adj[a].push_back(b);adj[b].push_back(a);}for (int i = 0; i < n; i++){u[i] = 1;cin >> u[i];}cin >> m;for (int i = 0; i < m; i++){cin >> query[i][0] >> query[i][1];query[i][2] = 1;}memset(parent, -1, sizeof(parent));memset(depth, -1, sizeof(depth));depth[0] = 0;dfs(0);func(0, -1, 0);for (int i = 0; i < 17; i++){for (int j = 1; j < n; j++){if (parent[j][i] != -1){parent[j][i + 1] = parent[parent[j][i]][i];}}}long long int res = 0;for (int i = 0; i < m; i++){a = query[i][0];b = query[i][1];c = query[i][2];long long int lca = getlca(a, b);//cout << a << ' ' << b << ' ' << lca << '\n';if (lca > 0){long long int sum = arr[a] - arr[parent[lca][0]];sum += (arr[b] - arr[lca]);res += (sum * c);}else{long long int sum = arr[a];sum += (arr[b] - arr[lca]);res += (sum * c);}}cout << res << '\n';return 0;}