#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef double long dl;
typedef vector<ll> row;
typedef vector< pair<ll,ll> > rowp;
typedef vector<row> grid;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define rep(i,a,b) for (ll i = a; i < b; i++)
#define pmod 1000000007
#define INF 100000000000000000
#define pi atan(1)*4
#define modi 1000000
#define nmod 998244353
#define salto '\n'
struct Tree{
private:
vector<rowp> tree;
vector<row> centroids;
ll n, root, rootc, ntemp;
vector<ll> siz;
bitset<200010> seen;
vector<rowp> sparse;
row rank;
ll ans = INF;
vector<ll> eliminar;
vector<ll> fatherc;
vector<ll> ramas[2];
ll actual;
rowp temp;
map<ll,ll> mini;
public:
//basic
void create(ll m){
n = m+1;
tree.assign(n, rowp());
centroids.assign(n, row());
siz.assign(n, 0);
sparse.assign(n, rowp(20, pll( {0,0} ) ));
rank.assign(n, 0);
fatherc.assign(n, 0);
ramas[0].assign(n, INF);
ramas[1].assign(n, INF);
for(ll i = 0; i < n; i++){
ramas[0][i] = INF;
ramas[1][i] = INF;
}
}
void add(ll u, ll v, ll w){
tree[u].PB({v, w});
tree[v].PB({u, w});
}
void addc(ll u, ll v){
centroids[u].PB(v);
centroids[v].PB(u);
}
//centroide
ll calc_size(ll u,ll p){
siz[u] = 1;
for(auto v : tree[u]){
if(v.F != p && !seen[v.F]) {
siz[u] += calc_size(v.F,u);
}
}
return siz[u];
}
ll disc_centroid(ll u,ll p){
for(auto v : tree[u]){
if(v.F == p || seen[v.F]) continue;
if(siz[v.F] > ntemp/2) return disc_centroid(v.F,u);
}
return u;
}
ll find_centroid(ll root, ll p){
ntemp = calc_size(root,p);
ll c = disc_centroid(root,p);
seen[c] = 1;
for(auto v : tree[c]){
if(seen[v.F]) continue;
ll temporal = find_centroid(v.F,c);
addc(c, temporal);
fatherc[temporal] = c;
}
return c;
}
//lca
void dfs(ll u, ll p, ll rango){
sparse[u][0].F = p;
rank[u] = rango;
for(auto v : tree[u]){
if(v.F == p) continue;
sparse[v.F][0].S = v.S;
dfs(v.F, u, rango+1);
}
}
void sparse_fill(){
for(ll i = 1; i < 20; i++){
for(ll j = 0; j < n; j++){
sparse[j][i].F = sparse[sparse[j][i-1].F][i-1].F;
sparse[j][i].S = sparse[j][i-1].S + sparse[sparse[j][i-1].F][i-1].S;
}
}
}
pll lca_calc(ll a, ll b){
if(rank[a] > rank[b]) swap(a,b);
pll ret = {0, 0};
ll dif = rank[b] - rank[a];
ll temp = 0, llevo = 1;
while(dif){
if(dif&1){
ret.F += llevo;
ret.S += sparse[b][temp].S;
b = sparse[b][temp].F;
}
llevo*= 2;
temp++;
dif = dif >> 1;
}
if(a == b) return ret;
llevo = (1 << 19);
for(ll i = 19; i >= 0; i--){
if(sparse[a][i].F != sparse[b][i].F){
ret.F += 2*llevo;
ret.S += sparse[a][i].S + sparse[b][i].S;
a = sparse[a][i].F;
b = sparse[b][i].F;
}
llevo/= 2;
}
ret.F+= 2;
ret.S += sparse[a][0].S + sparse[b][0].S;
return ret;
}
//procesos
void pre_calcular(){
//lca
dfs(1, 0, 0);
sparse_fill();
//centroids
rootc = find_centroid(1, 0);
fatherc[rootc] = 0;
}
void delet(){
ans = INF;
ll tempo;
while(eliminar.size()){
tempo = eliminar.back(); eliminar.pop_back();
ramas[0][tempo] = INF;
ramas[1][tempo] = INF;
}
}
void evaluate(ll fact, ll type){
pll me;
ll ori = fact;
while(fact != 0){
eliminar.PB(fact);
me = lca_calc(ori, fact);
ramas[type][fact] = min(ramas[type][fact], me.S);
if(ramas[ (type+1)%2 ][fact] != INF){
ans = min(ans, ramas[0][fact] + ramas[1][fact]);
}
fact = fatherc[fact];
}
}
ll answer(){
return ans;
}
};
Tree arbol;
void Init(int N, int A[], int B[], int D[]){
arbol.create(N);
for(ll i = 0; i+1 < N; i++){
arbol.add(A[i]+1, B[i]+1, D[i]);
}
arbol.pre_calcular();
}
ll Query(int S, int X[], int T, int Y[]){
arbol.delet();
for(ll i = 0; i < S; i++){
arbol.evaluate(X[i]+1, 0);
}
for(ll i = 0; i < T; i++){
arbol.evaluate(Y[i]+1, 1);
}
return arbol.answer();
}
void solve(){
ll n, q;
cin >> n >> q;
Tree arbol;
arbol.create(n+1);
ll u, v, w;
for(ll i = 1; i < n; i++){
cin >> u >> v >> w;
u++; v++;
arbol.add(u,v,w);
}
arbol.pre_calcular();
ll s, t, temp;
for(ll i = 0; i < q; i++){
arbol.delet();
cin >> s >> t;
for(ll i2 = 0; i2 < s; i2++){
cin >> temp;
temp++;
arbol.evaluate(temp, 0);
}
for(ll i2 = 0; i2 < t; i2++){
cin >> temp;
temp++;
arbol.evaluate(temp, 1);
}
cout << arbol.answer() << endl;
}
}
/*
int main(){
//ifstream fin ("text.in");
//ofstream fout ("text.out");
ll t = 1;
while(t--) solve();
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
844 KB |
Output is correct |
| 2 |
Correct |
784 ms |
11240 KB |
Output is correct |
| 3 |
Correct |
1714 ms |
20612 KB |
Output is correct |
| 4 |
Correct |
1724 ms |
21044 KB |
Output is correct |
| 5 |
Correct |
1929 ms |
21184 KB |
Output is correct |
| 6 |
Correct |
349 ms |
20536 KB |
Output is correct |
| 7 |
Correct |
1813 ms |
20628 KB |
Output is correct |
| 8 |
Correct |
1902 ms |
21040 KB |
Output is correct |
| 9 |
Correct |
1992 ms |
21184 KB |
Output is correct |
| 10 |
Correct |
322 ms |
20532 KB |
Output is correct |
| 11 |
Correct |
1818 ms |
20504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
588 KB |
Output is correct |
| 2 |
Runtime error |
1854 ms |
524288 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
844 KB |
Output is correct |
| 2 |
Correct |
784 ms |
11240 KB |
Output is correct |
| 3 |
Correct |
1714 ms |
20612 KB |
Output is correct |
| 4 |
Correct |
1724 ms |
21044 KB |
Output is correct |
| 5 |
Correct |
1929 ms |
21184 KB |
Output is correct |
| 6 |
Correct |
349 ms |
20536 KB |
Output is correct |
| 7 |
Correct |
1813 ms |
20628 KB |
Output is correct |
| 8 |
Correct |
1902 ms |
21040 KB |
Output is correct |
| 9 |
Correct |
1992 ms |
21184 KB |
Output is correct |
| 10 |
Correct |
322 ms |
20532 KB |
Output is correct |
| 11 |
Correct |
1818 ms |
20504 KB |
Output is correct |
| 12 |
Correct |
3 ms |
588 KB |
Output is correct |
| 13 |
Runtime error |
1854 ms |
524288 KB |
Execution killed with signal 11 |
| 14 |
Halted |
0 ms |
0 KB |
- |
