#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)
const ll INF = 1e18;
const int N = 5e5+3, Q = 1e5+3;
int n, q;
vector<ii> adj[N];
namespace tree {
int spt[N][20], lev[N];
ll depth[N];
void dfs(int s = 0, int e = -1) {
spt[s][0] = e;
for (auto [u,w] : adj[s]) if (u != e) {
depth[u] += depth[s]+w, lev[u] = lev[s]+1, dfs(u,s);
}
}
void build() {
dfs();
rep(j,1,19) rep(i,0,n-1) spt[i][j] = spt[spt[i][j-1]][j-1];
}
int lca(int x, int y) {
if (lev[x] > lev[y]) swap(x,y);
rep(i,0,19) if ((lev[y]-lev[x])>>i&1) y = spt[y][i];
if (x == y) return x;
per(i,0,19) {
if (spt[x][i] != spt[y][i])
x = spt[x][i], y = spt[y][i];
}
return spt[x][0];
}
ll dist(int x, int y) { return depth[x]+depth[y]-2*depth[lca(x,y)]; }
}
namespace centroid_tree {
int sub[N], par[N];
bool erased[N];
void size_calc(int s, int e = -1) {
sub[s] = 1;
for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
size_calc(u,s), sub[s] += sub[u];
}
}
int centroid(int S, int s, int e = -1) {
for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
if (sub[u] > S/2) return centroid(S,u,s);
}
return s;
}
ll dist[N]{};
void build(int s = 0, int e = -1) {
size_calc(s);
int c = centroid(sub[s],s);
dist[c] = INF;
erased[c] = true, par[c] = e;
for (auto [u,w] : adj[c]) if (not erased[u]) {
build(u,c);
}
}
ll query(int x) {
ll res = INF;
for (int y = x; y != -1; y = par[y]) {
mup(res, dist[y]+tree::dist(x,y));
}
return res;
}
void update(int x) {
for (int y = x; y != -1; y = par[y]) {
mup(dist[y], tree::dist(x,y));
}
}
void clear(int x) {
for (int y = x; y != -1; y = par[y]) dist[y] = INF;
}
};
void Init(int N, int A[], int B[], int D[]) {
rep(i,0,N-2) {
auto [u,v,w] = tie(A[i],B[i],D[i]);
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
tree::build();
centroid_tree::build();
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> x(S);
ll ans = INF;
rep(i,0,S-1) centroid_tree::update(X[i]);
rep(i,0,T-1) mup(ans, centroid_tree::query(Y[i]));
rep(i,0,S-1) centroid_tree::clear(X[i]);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
12620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
12196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
12620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
