//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const ll inf = 1e15;
const int mod = 1e9+7;
const int maxn = 5e3 + 3;
//#include "factories.h"
int dp[maxn], up[maxn][18], sz[maxn], cup[maxn];
ll p[maxn], dst[maxn];
vt<pii> g[maxn];
vt<int> rst;
bool first;
void dfs(int v){
sz[v] = 1;
for(auto i : g[v]){
if(i.ff != up[v][0]){
up[i.ff][0] = v;
dp[i.ff] = dp[v] + 1;
p[i.ff] = p[v] + i.ss;
dfs(i.ff);
sz[v] += sz[i.ff];
}
}
}
void cd(int v, int m){
for(auto i : g[v]){
if(sz[i.ff] > m / 2){
sz[v] = m - sz[i.ff];
cd(i.ff, m);
return;
}
}
if(!first){
first = 1;
cup[v] = -1;
}
//cout << v << ' ';
sz[v] = -1;
for(auto i : g[v]){
if(sz[i.ff] != -1){
cup[i.ff] = v;
cd(i.ff, sz[i.ff]);
}
}
}
ll dist(int x, int y){
if(dp[x] > dp[y])swap(x, y);
int a = x, b = y;
for(int j = 17; j >= 0; j--){
if(((dp[b] - dp[a]) >> j) & 1){
b = up[b][j];
}
}
if(a == b){
ll q = p[x] - p[a] + p[y] - p[a];
return q;
}
for(int j = 17; j >= 0; j--){
if(up[b][j] != up[a][j]){
a = up[a][j], b = up[b][j];
}
}
a = up[a][0];
ll q = p[x] - p[a] + p[y] - p[a];
return q;
}
void Init(int n, int a[], int b[], int d[]) {
for(int i = 0; i < n - 1; i++){
g[a[i]].pb({b[i], d[i]});
g[b[i]].pb({a[i], d[i]});
}
first = 0;
dfs(0);
for(int j = 1; j < 18; j++){
for(int i = 0; i < n; i++)up[i][j] = up[up[i][j - 1]][j - 1];
}
cd(0, n);
for(int i = 0; i < n; i++)dst[i] = inf;
}
long long Query(int s, int x[], int t, int y[]) {
ll ret = inf;
for(int i = 0; i < s; i++){
int par = x[i];
while(par != -1){
if(dst[par] == inf)rst.pb(par);
dst[par] = min(dst[par], dist(x[i], par));
par = cup[par];
}
}
for(int i = 0; i < t; i++){
int par = y[i];
while(par != -1){
ret = min(ret, dst[par] + dist(par, y[i]));
par = cup[par];
}
}
for(auto i : rst)dst[i] = inf;
rst.clear();
return ret;
}
//void solve() {
//int n, q;
//cin >> n >> q;
//int a[n - 1], b[n - 1], d[n - 1];
//for(int i = 0; i < n - 1; i++){
//cin >> a[i] >> b[i] >> d[i];
//}
//Init(n, a, b, d);
//for(int i = 0; i < q; i++){
//int s, t;
//cin >> s >> t;
//int x[s], y[t];
//for(int j = 0; j < s; j++)cin >> x[j];
//for(int j = 0; j < t; j++)cin >> y[j];
//cout << Query(s, x, t, y) << '\n';
//}
//}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int times = 1;
////cin >> times;
//for(int i = 1; i <= times; i++) {
//solve();
//}
//return 0;
//}
//7 3
//0 1 4
//1 2 4
//2 3 5
//2 4 6
//4 5 5
//1 6 3
//2 2
//0 6
//3 4
//3 2
//0 1 3
//4 6
//1 1
//2
//5
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
8035 ms |
19012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
8053 ms |
19036 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
8035 ms |
19012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
