結果

問題 No.386 貪欲な領主
ユーザー legendcn666legendcn666
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# 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 second
const 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0