結果

問題 No.386 貪欲な領主
ユーザー Konton7
提出日時 2020-02-03 23:49:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 755 ms / 2,000 ms
コード長 3,669 bytes
コンパイル時間 2,084 ms
コンパイル使用メモリ 203,916 KB
最終ジャッジ日時 2025-01-08 22:00:58
ジャッジサーバーID
(参考情報)
judge1 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int amax = 18;
struct node
{
int depth;
vector<ll> custom;
vector<ll> ansestors;
vector<ll> childrens;
vector<ll> roads;
};
vector<node> nodes;
void dfs(ll s, ll d)
{
nodes[s].depth = d;
for (auto z : nodes[s].roads)
{
if (nodes[z].depth == -1)
{
dfs(z, d + 1);
nodes[s].childrens.push_back(z);
}
else
{
nodes[s].ansestors[0] = z;
}
}
}
ll cost_to_ansestors(ll s, ll n)
{
ll m, c;
c = 0;
if (n == 0)
return 0;
else
{
m = n;
while (m > 0 && m % 2 == 0)
{
c++;
m /= 2;
}
return nodes[s].custom[c] + cost_to_ansestors(nodes[s].ansestors[c], n - pow(2, c));
}
}
ll back_to_ansestors(ll s, ll n)
{
ll m, c;
c = 0;
if (n == 0)
return s;
else
{
m = n;
while (m > 0 && m % 2 == 0)
{
c++;
m /= 2;
}
return back_to_ansestors(nodes[s].ansestors[c], n - pow(2, c));
}
}
ll lca(ll a, ll b)
{
ll dd, ok, ng, mid;
dd = nodes[a].depth - nodes[b].depth;
if (dd > 0)
a = back_to_ansestors(a, dd);
if (dd < 0)
b = back_to_ansestors(b, abs(dd));
if (a == b)
return a;
if (a == 0 || b == 0)
return 0;
while (nodes[a].ansestors[0] != nodes[b].ansestors[0])
{
for (int i = amax - 1; i > -1; i--)
{
if (nodes[a].ansestors[i] != nodes[b].ansestors[i])
{
a = nodes[a].ansestors[i];
b = nodes[b].ansestors[i];
break;
}
}
}
return nodes[a].ansestors[0];
}
int main()
{
#ifdef DEBUG
cout << "DEBUG MODE" << endl;
ifstream in("input.txt"); //for debug
cin.rdbuf(in.rdbuf()); //for debug
#endif
ll n, k, q, a, b, c, d, ans;
cin >> n;
vector<ll> cusint, ainit, cinit, rinit;
rep(i, n)
{
nodes.push_back((node){-1, cusint, ainit, cinit, rinit});
}
rep(i, n - 1)
{
cin >> a >> b;
nodes[a].roads.push_back(b);
nodes[b].roads.push_back(a);
}
rep(i, n)
{
rep(j, amax)
{
nodes[i].custom.push_back(0);
nodes[i].ansestors.push_back(-1);
}
cin >> k;
nodes[i].custom[0] = k;
}
dfs(0, 0);
rep(j, amax - 1)
{
rep(i, n)
{
if (nodes[i].ansestors[j] != -1 && nodes[nodes[i].ansestors[j]].ansestors[j] != -1)
{
nodes[i].ansestors[j + 1] = nodes[nodes[i].ansestors[j]].ansestors[j];
nodes[i].custom[j + 1] = nodes[nodes[i].ansestors[j]].custom[j] + nodes[i].custom[j];
}
}
}
ans = 0;
cin >> q;
rep(i, q)
{
cin >> a >> b >> c;
d = lca(a, b);
ans += c * nodes[d].custom[0];
ans += c * cost_to_ansestors(a, nodes[a].depth - nodes[d].depth);
ans += c * cost_to_ansestors(b, nodes[b].depth - nodes[d].depth);
}
cout << ans << endl;
// rep(i, n)
// {
// cout << nodes[i].depth << "\t";
// rep(j, amax)
// {
// cout << nodes[i].custom[j] << " ";
// }
// cout << "\t" << cost_to_ansestors(i, nodes[i].depth);
// cout << endl;
// }
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0