#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int long long
const int N = 1e5 + 5;
const int M = 1e9 + 5;
const int MAXN = 505;
struct ST{
long long tree[N * 60];
int ch[N * 60][2], last;
ST(){
last = 0;
}
int bala(int x, int t){
if(!ch[x][t]){
ch[x][t] = ++last;
}
return ch[x][t];
}
void add(int l, int r, long long v, int lx = 0, int rx = M, int x = 0){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
tree[x] += v;
return;
} int m = (lx + rx) >> 1;
add(l, r, v, lx, m, bala(x, 0));
add(l, r, v, m+1, rx, bala(x, 1));
}
long long get(int i, int lx = 0, int rx = M, int x = 0){
if(lx == rx) return tree[x];
int m = (lx + rx) >> 1;
if(i <= m && ch[x][0]) return tree[x] + get(i, lx, m, ch[x][0]);
if(m < i && ch[x][1]) return tree[x] + get(i, m+1, rx, ch[x][1]);
return tree[x];
}
}tree, cnt;
int a[N], b[N], w[N];
vector<int> edges[MAXN];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin>>n>>m;
vector<int> p(m);
for(int i=0;i<m;i++){ p[i] = i;
cin>>a[i]>>b[i]>>w[i];
}
sort(p.begin(), p.end(), [&](int i, int j){
return (w[i] > w[j]);
});
auto er = [&](vector<int>& a, int v){
auto it = lower_bound(a.begin(), a.end(), v);
a.erase(it);
};
w[m] = -1;
for(auto i : p){
int in = -1, R = w[i];
function<void(int, int, int)> dfs = [&](int u, int ed, int p){
if(u == b[i]){
in = ed;
return;
}
for(auto j : edges[u]){
int x = a[j] ^ b[j] ^ u;
if(x == p) continue;
int tmp = ed;
if(w[j] > w[ed]) tmp = j;
else if(w[j] == w[ed] && j > ed) tmp = j;
dfs(x, tmp, u);
if(~in) return;
}
};
dfs(a[i], m, a[i]);
if(in == -1){
R = M;
} else {
R = (w[i] + w[in]) / 2;
if((w[in]&1) == (w[i]&1) && in < i) R--;
er(edges[a[in]], in);
er(edges[b[in]], in);
}
if(w[i] <= R){
tree.add(w[i], R, -w[i]);
cnt.add(w[i], R, 1);
}
edges[a[i]].push_back(i);
sort(edges[a[i]].begin(), edges[a[i]].end());
edges[b[i]].push_back(i);
sort(edges[b[i]].begin(), edges[b[i]].end());
}
sort(p.begin(), p.end(), [&](int i, int j){
return (w[i] < w[j]);
});
for(int i=1;i<=n;i++) edges[i].clear();
w[m] = M;
for(auto i : p){
int in = -1, L = w[i];
function<void(int, int, int)> dfs = [&](int u, int ed, int p){
if(u == b[i]){
in = ed;
return;
}
for(auto j : edges[u]){
int x = a[j] ^ b[j] ^ u;
if(x == p) continue;
int tmp = ed;
if(w[j] < w[ed]) tmp = j;
else if(w[j] == w[ed] && j > ed) tmp = j;
dfs(x, tmp, u);
if(~in) return;
}
};
dfs(a[i], m, a[i]);
assert(in != m);
if(in == -1){
L = 0;
} else {
L = (w[i] + w[in] + 1) / 2;
if((w[in]&1) == (w[i]&1) && in < i) L++;
er(edges[a[in]], in);
er(edges[b[in]], in);
}
if(L <= w[i]){
tree.add(L, w[i], w[i]);
cnt.add(L, w[i], -1);
}
edges[a[i]].push_back(i);
sort(edges[a[i]].begin(), edges[a[i]].end());
edges[b[i]].push_back(i);
sort(edges[b[i]].begin(), edges[b[i]].end());
}
int q; cin>>q;
while(q--){
long long x; cin>>x;
cout<<tree.get(x) + cnt.get(x) * x<<"\n";
}
}
/*
2 4 15
1 3 13
1 5 11
1 2 8
2 3 7
3 4 6
3 5 6
1 4 5
1 5 3
4 5 2
5 10
1 2 8
1 3 13
1 4 5
1 5 11
1 5 3
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
2
6
3
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
420 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
392 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
420 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
392 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2303 ms |
227080 KB |
Output is correct |
21 |
Correct |
1091 ms |
227032 KB |
Output is correct |
22 |
Correct |
1311 ms |
227164 KB |
Output is correct |
23 |
Correct |
1441 ms |
226992 KB |
Output is correct |
24 |
Correct |
1633 ms |
227132 KB |
Output is correct |
25 |
Correct |
2005 ms |
227068 KB |
Output is correct |
26 |
Correct |
2024 ms |
228836 KB |
Output is correct |
27 |
Correct |
2009 ms |
221372 KB |
Output is correct |
28 |
Incorrect |
1757 ms |
8860 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1547 ms |
244620 KB |
Output is correct |
5 |
Correct |
1659 ms |
244980 KB |
Output is correct |
6 |
Correct |
1738 ms |
244452 KB |
Output is correct |
7 |
Correct |
945 ms |
246256 KB |
Output is correct |
8 |
Correct |
897 ms |
246836 KB |
Output is correct |
9 |
Correct |
836 ms |
246228 KB |
Output is correct |
10 |
Correct |
1568 ms |
244036 KB |
Output is correct |
11 |
Correct |
793 ms |
245976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
420 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
392 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
295 ms |
23940 KB |
Output is correct |
21 |
Correct |
267 ms |
19212 KB |
Output is correct |
22 |
Correct |
302 ms |
23916 KB |
Output is correct |
23 |
Correct |
263 ms |
24832 KB |
Output is correct |
24 |
Correct |
250 ms |
24724 KB |
Output is correct |
25 |
Correct |
261 ms |
24524 KB |
Output is correct |
26 |
Correct |
251 ms |
23664 KB |
Output is correct |
27 |
Incorrect |
226 ms |
22152 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
420 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
392 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2303 ms |
227080 KB |
Output is correct |
21 |
Correct |
1091 ms |
227032 KB |
Output is correct |
22 |
Correct |
1311 ms |
227164 KB |
Output is correct |
23 |
Correct |
1441 ms |
226992 KB |
Output is correct |
24 |
Correct |
1633 ms |
227132 KB |
Output is correct |
25 |
Correct |
2005 ms |
227068 KB |
Output is correct |
26 |
Correct |
2024 ms |
228836 KB |
Output is correct |
27 |
Correct |
2009 ms |
221372 KB |
Output is correct |
28 |
Incorrect |
1757 ms |
8860 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
420 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
392 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
2303 ms |
227080 KB |
Output is correct |
21 |
Correct |
1091 ms |
227032 KB |
Output is correct |
22 |
Correct |
1311 ms |
227164 KB |
Output is correct |
23 |
Correct |
1441 ms |
226992 KB |
Output is correct |
24 |
Correct |
1633 ms |
227132 KB |
Output is correct |
25 |
Correct |
2005 ms |
227068 KB |
Output is correct |
26 |
Correct |
2024 ms |
228836 KB |
Output is correct |
27 |
Correct |
2009 ms |
221372 KB |
Output is correct |
28 |
Incorrect |
1757 ms |
8860 KB |
Output isn't correct |
29 |
Halted |
0 ms |
0 KB |
- |