#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());
}
reverse(p.begin(), p.end());
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 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
