QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253242 | #5313. Please Save Pigeland | KULIANLEN | RE | 0ms | 24068kb | C++14 | 3.4kb | 2023-11-16 20:07:37 | 2023-11-16 20:07:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 5e5 + 5,INF = 1e18;
#define ls (u << 1)
#define rs (u << 1 | 1)
#define sum(u) (tr[u].sum)
#define d(u) (tr[u].d)
#define tot(u) (tr[u].tot)
#define mk(u) (tr[u].mk)
struct node{
int l,r;
int sum,d;
int tot,mk;
}tr[N << 2];
int a[N],b[N];
void pushup(int u)
{
sum(u) = sum(ls) + sum(rs);tot(u) = tot(ls) + tot(rs);
d(u) = __gcd(d(ls), d(rs));
}
void pushdown(int u)
{
tot(ls) += mk(u) * (tr[ls].r - tr[ls].l + 1);
tot(rs) += mk(u) * (tr[rs].r - tr[rs].l + 1);
mk(ls) += mk(u);mk(rs) += mk(u);
mk(u) = 0;
}
void build(int u,int l,int r)
{
if(l == r)tr[u] = {l, l, a[l], a[l], b[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
}
void upd2(int u,int l,int r,int d)
{
if(tr[u].l >= l && tr[u].r <= r)
{
tot(u) += d * (tr[u].r - tr[u].l + 1);
mk(u) += d;
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid)upd2(ls, l, r, d);
if(r > mid)upd2(rs, l, r, d);
pushup(u);
}
}
void upd(int u,int x,int d)
{
if(tr[u].l == tr[u].r)
{
sum(u) += d;
d(u) += d;
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid)upd(ls, x, d);
else upd(rs, x, d);
pushup(u);
}
}
node que(int u,int l,int r)
{
if(tr[u].l >= l && tr[u].r <= r)
{
return tr[u];
}
else
{
int mid = tr[u].l + tr[u].r >> 1;
node res = {0,0,0,0,0,0};
if(l <= mid)
{
res = que(ls, l, r);
}
if(r > mid)
{
node tmp = que(rs ,l ,r);
res.sum += tmp.sum;
res.d = __gcd(res.d, tmp.d);
res.tot += tmp.tot;
}
return res;
}
}
int quesum(int l,int r)
{
return que(1, l, r).sum;
}
int quegcd(int l,int r)
{
int sum = 0;
sum = que(1, 1, l).sum;
int d = 0;
if(l != r)
d = que(1, l + 1, r).d;
// cout <<l <<" " << r <<" "<< sum <<" " << d << " " << abs(__gcd(sum,d)) <<" " << "Dsa" << endl;
return abs(__gcd(sum, d));
}
bool st[N];vector<pair<int,int>> g[N];
int cnt,dfsn[N],rdfsn[N],n,k;
void dfs(int u,int f,int d)
{
dfsn[u] = INF;
if(st[u])dfsn[u] = ++cnt,rdfsn[u] = cnt,b[dfsn[u]] = d;
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
dfs(to, u, d + val);
dfsn[u] = min(dfsn[u], dfsn[to]);
rdfsn[u] = max(rdfsn[to], rdfsn[u]);
}
}
void upd1(int l,int r,int x)
{
if(l < 1 || r > k || l > r)return;
upd(1, l, x);
upd2(1, l, r, x);
if(r + 1 <= k)upd(1, r + 1, -x);
}
int ans = 1e18;
void dfs1(int u,int f)
{
int res = quegcd(1,k);
int dis = tr[1].tot;
// cout << u <<" " << res <<" " << dis << endl;
ans = min(ans, dis / res);
for(auto t : g[u])
{
int to = t.first,val = t.second;
if(to == f)continue;
int l = dfsn[to],r = rdfsn[to];
if(l <= r)
{
upd1(l, r, -val);
upd1(1, l - 1, val);
upd1(r + 1, k, val);
dfs1(to, u);
upd1(l, r, val);
upd1(1, l - 1, -val);
upd1(r + 1, k, -val);
}
else
{
upd1(1, k, val);
dfs1(to, u);
upd1(1, k, -val);
}
}
}
signed main()
{
cin >> n >> k;
for(int i = 1;i <= k;i++)
{
int t;cin >> t;st[t] = true;
}
for(int i = 1;i < n;i++)
{
int u,v,w;cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dfs(1,0,0);
for(int i = 1;i <= k;i++)a[i] = b[i] - b[i - 1];
build(1,1,k);
if(n!=1)
dfs1(1,0);
else ans = 0;
cout << ans * 2 << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 24044kb
input:
5 3 3 4 5 1 2 2 2 3 4 2 5 4 3 4 6
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 0ms
memory: 24044kb
input:
10 3 1 7 10 7 6 3 1 8 3 3 6 3 8 6 2 4 1 1 10 6 4 2 8 3 9 10 3 5 10 3
output:
24
result:
ok 1 number(s): "24"
Test #3:
score: 0
Accepted
time: 0ms
memory: 24068kb
input:
1 1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Runtime Error
input:
100000 1 79187 72704 72659 15 32741 43496 10 21580 97447 17 55758 36700 21 32116 3643 14 60460 58764 12 75894 50624 7 58295 49393 22 43733 17210 1 58093 68769 15 1086 58916 17 25632 37710 11 49555 92976 8 32547 27060 18 84896 12811 1 3196 1242 16 18870 78236 14 2414 7945 12 48745 15399 1 17648 83791...