結果
| 問題 | No.1442 I-wate Shortest Path Problem |
| ユーザー |
 LayCurse
|
| 提出日時 | 2021-03-26 21:44:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 626 ms / 3,000 ms |
| コード長 | 28,673 bytes |
| コンパイル時間 | 3,930 ms |
| コンパイル使用メモリ | 234,056 KB |
| 実行使用メモリ | 45,760 KB |
| 最終ジャッジ日時 | 2024-05-06 15:06:40 |
| 合計ジャッジ時間 | 13,308 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4 ms
13,768 KB |
| testcase_01 | AC | 4 ms
13,772 KB |
| testcase_02 | AC | 7 ms
11,824 KB |
| testcase_03 | AC | 51 ms
14,904 KB |
| testcase_04 | AC | 8 ms
17,904 KB |
| testcase_05 | AC | 6 ms
11,800 KB |
| testcase_06 | AC | 50 ms
20,708 KB |
| testcase_07 | AC | 7 ms
13,872 KB |
| testcase_08 | AC | 41 ms
13,824 KB |
| testcase_09 | AC | 11 ms
18,072 KB |
| testcase_10 | AC | 53 ms
22,908 KB |
| testcase_11 | AC | 52 ms
16,324 KB |
| testcase_12 | AC | 322 ms
39,164 KB |
| testcase_13 | AC | 142 ms
32,772 KB |
| testcase_14 | AC | 239 ms
34,836 KB |
| testcase_15 | AC | 240 ms
36,964 KB |
| testcase_16 | AC | 355 ms
42,004 KB |
| testcase_17 | AC | 613 ms
42,004 KB |
| testcase_18 | AC | 626 ms
41,432 KB |
| testcase_19 | AC | 375 ms
42,000 KB |
| testcase_20 | AC | 610 ms
42,008 KB |
| testcase_21 | AC | 596 ms
41,608 KB |
| testcase_22 | AC | 134 ms
29,008 KB |
| testcase_23 | AC | 311 ms
35,116 KB |
| testcase_24 | AC | 78 ms
41,416 KB |
| testcase_25 | AC | 276 ms
45,760 KB |
| testcase_26 | AC | 77 ms
33,616 KB |
コンパイルメッセージ
main.cpp: In member function 'T segtree<T>::getSum(int, int) [with T = long long int]':
main.cpp:675:7: warning: 'res' may be used uninitialized [-Wmaybe-uninitialized]
675 | T res;
| ^~~
main.cpp:714:11: warning: 'tmp' may be used uninitialized [-Wmaybe-uninitialized]
714 | res = res + tmp;
| ~~~~^~~~~~~~~~~
main.cpp:676:7: note: 'tmp' was declared here
676 | T tmp;
| ^~~
ソースコード
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void*wmem;
char memarr[96000000];
template<class S, class T> inline S min_L(S a,T b){
return a<=b?a:b;
}
template<class S, class T> inline S max_L(S a,T b){
return a>=b?a:b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
(*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
(*arr)=(T*)(*mem);
(*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
walloc1d(arr, x2-x1, mem);
(*arr) -= x1;
}
inline int my_getchar_unlocked(){
static char buf[1048576];
static int s = 1048576;
static int e = 1048576;
if(s == e && e == 1048576){
e = fread_unlocked(buf, 1, 1048576, stdin);
s = 0;
}
if(s == e){
return EOF;
}
return buf[s++];
}
inline void rd(int &x){
int k;
int m=0;
x=0;
for(;;){
k = my_getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = my_getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline void rd(long long &x){
int k;
int m=0;
x=0;
for(;;){
k = my_getchar_unlocked();
if(k=='-'){
m=1;
break;
}
if('0'<=k&&k<='9'){
x=k-'0';
break;
}
}
for(;;){
k = my_getchar_unlocked();
if(k<'0'||k>'9'){
break;
}
x=x*10+k-'0';
}
if(m){
x=-x;
}
}
inline int rd_int(void){
int x;
rd(x);
return x;
}
struct MY_WRITER{
char buf[1048576];
int s;
int e;
MY_WRITER(){
s = 0;
e = 1048576;
}
~MY_WRITER(){
if(s){
fwrite_unlocked(buf, 1, s, stdout);
}
}
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
MY_WRITER_VAR.s = 0;
}
MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
my_putchar_unlocked(a);
}
inline void wt_L(long long x){
int s=0;
int m=0;
char f[20];
if(x<0){
m=1;
x=-x;
}
while(x){
f[s++]=x%10;
x/=10;
}
if(!s){
f[s++]=0;
}
if(m){
my_putchar_unlocked('-');
}
while(s--){
my_putchar_unlocked(f[s]+'0');
}
}
template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
a[k] = aval;
}
template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
for(i=sz-1;i>k;i--){
b[i] = b[i-1];
}
a[k] = aval;
b[k] = bval;
}
template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
for(i=sz-1;i>k;i--){
b[i] = b[i-1];
}
for(i=sz-1;i>k;i--){
c[i] = c[i-1];
}
a[k] = aval;
b[k] = bval;
c[k] = cval;
}
template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
int i;
sz++;
for(i=sz-1;i>k;i--){
a[i] = a[i-1];
}
for(i=sz-1;i>k;i--){
b[i] = b[i-1];
}
for(i=sz-1;i>k;i--){
c[i] = c[i-1];
}
for(i=sz-1;i>k;i--){
d[i] = d[i-1];
}
a[k] = aval;
b[k] = bval;
c[k] = cval;
d[k] = dval;
}
template<class S, class T> inline S chmin(S &a, T b){
if(a>b){
a=b;
}
return a;
}
template <class T> struct DijkstraHeap{
int*hp;
int*place;
int size;
char*visited;
T*val;
void malloc(int N){
hp = (int*)std::malloc(N*sizeof(int));
place = (int*)std::malloc(N*sizeof(int));
visited = (char*)std::malloc(N*sizeof(char));
val = (T*)std::malloc(N*sizeof(T));
}
void free(){
std::free(hp);
std::free(place);
std::free(visited);
std::free(val);
}
void walloc(int N, void **mem=&wmem){
walloc1d(&hp, N, mem);
walloc1d(&place, N, mem);
walloc1d(&visited, N, mem);
walloc1d(&val, N, mem);
}
void init(int N){
int i;
size = 0;
for(i=(0);i<(N);i++){
place[i]=-1;
}
for(i=(0);i<(N);i++){
visited[i]=0;
}
}
void up(int n){
int m;
while(n){
m=(n-1)/2;
if(val[hp[m]]<=val[hp[n]]){
break;
}
swap(hp[m],hp[n]);
swap(place[hp[m]],place[hp[n]]);
n=m;
}
}
void down(int n){
int m;
for(;;){
m=2*n+1;
if(m>=size){
break;
}
if(m+1<size&&val[hp[m]]>val[hp[m+1]]){
m++;
}
if(val[hp[m]]>=val[hp[n]]){
break;
}
swap(hp[m],hp[n]);
swap(place[hp[m]],place[hp[n]]);
n=m;
}
}
void change(int n, T v){
if(visited[n]||(place[n]>=0&&val[n]<=v)){
return;
}
val[n]=v;
if(place[n]==-1){
place[n]=size;
hp[size++]=n;
up(place[n]);
}
else{
up(place[n]);
}
}
int pop(void){
int res=hp[0];
place[res]=-1;
size--;
if(size){
hp[0]=hp[size];
place[hp[0]]=0;
down(0);
}
visited[res]=1;
return res;
}
}
;
template<class T> struct segtree{
int N;
int logN;
T*sum;
T*mn;
int*mnind;
T*fixval;
char*fixed;
T*addval;
void malloc(int maxN, int once = 0){
int i;
for(i=1;i<maxN;i*=2){
;
}
sum = new T[2*i];
mn = new T[2*i];
mnind = new int[2*i];
fixval = new T[i];
addval = new T[i];
fixed = new char[i];
if(once){
setN(maxN);
}
}
void walloc(int maxN, int once = 0, void **mem = &wmem){
int i;
for(i=1;i<maxN;i*=2){
;
}
walloc1d(&sum, 2*i, mem);
walloc1d(&mn, 2*i, mem);
walloc1d(&mnind, 2*i, mem);
walloc1d(&fixval, i, mem);
walloc1d(&addval, i, mem);
walloc1d(&fixed, i, mem);
if(once){
setN(maxN);
}
}
void free(void){
delete [] sum;
delete [] mn;
delete [] mnind;
delete [] fixval;
delete [] addval;
delete [] fixed;
}
T& operator[](int i){
return sum[N+i];
}
void setN(int n, int zerofill = 1, int dobuild = 1){
int i;
for(i=1,logN=0;i<n;i*=2,logN++){
;
}
N = i;
if(zerofill){
for(i=(0);i<(N);i++){
sum[N+i] = 0;
}
}
if(dobuild){
build();
}
}
void build(void){
int i;
for(i=(0);i<(N);i++){
mn[N+i] = sum[N+i];
mnind[N+i] = i;
}
for(i=N-1;i;i--){
sum[i] = sum[2*i] + sum[2*i+1];
if(mn[2*i] <= mn[2*i+1]){
mn[i] = mn[2*i];
mnind[i] = mnind[2*i];
}
else{
mn[i] = mn[2*i+1];
mnind[i] = mnind[2*i+1];
}
}
int o0VCpjj8 = N;
for(i=(1);i<(o0VCpjj8);i++){
fixed[i] = 0;
}
int vzsjNTAU = N;
for(i=(1);i<(vzsjNTAU);i++){
addval[i] = 0;
}
}
inline void push_one(int a, int sz, int st){
if(fixed[a]){
if(sz > 1){
fixed[a*2] = fixed[a*2+1] = 1;
fixval[a*2] = fixval[a*2+1] = fixval[a];
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
else{
sum[a*2] = sum[a*2+1] = sz * fixval[a];
mn[a*2] = mn[a*2+1] = fixval[a];
mnind[a*2] = st;
mnind[a*2+1] = st + sz;
}
fixed[a] = 0;
addval[a] = 0;
return;
}
if(addval[a] != 0){
if(sz > 1){
if(fixed[a*2]){
fixval[a*2] += addval[a];
}
else{
addval[a*2] += addval[a];
}
if(fixed[a*2+1]){
fixval[a*2+1] += addval[a];
}
else{
addval[a*2+1] += addval[a];
}
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
else{
sum[a*2] += sz * addval[a];
sum[a*2+1] += sz * addval[a];
mn[a*2] += addval[a];
mn[a*2+1] += addval[a];
}
addval[a] = 0;
return;
}
}
inline void push(int a){
int i;
int aa = a - N;
int nd;
int sz;
int st;
for(i=logN;i;i--){
nd = a>>i;
sz = 1<<(i-1);
st = 2 * sz * (aa>>i);
push_one(nd, sz, st);
}
}
inline void build(int a){
int sz = 1;
int st = a - N;
while(a > 1){
if(a%2){
st += sz;
}
a /= 2;
sz *= 2;
if(fixed[a]){
sum[a] = sz * fixval[a];
mn[a] = fixval[a];
}
else{
sum[a] = sum[a*2] + sum[a*2+1];
if(mn[a*2] <= mn[a*2+1]){
mn[a] = mn[a*2];
mnind[a] = mnind[a*2];
}
else{
mn[a] = mn[a*2+1];
mnind[a] = mnind[a*2+1];
}
if(addval[a] != 0){
mn[a] += addval[a];
sum[a] += sz * addval[a];
}
}
}
}
inline void change(int a, int b, T val){
int sz = 1;
int aa;
int bb;
int st_a = a;
int st_b = b;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] = mn[a] = val;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
sum[b] = mn[b] = val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
fixed[a]=1;
fixval[a]=val;
sum[a] = sz * val;
mn[a] = val;
mnind[a] = st_a;
a++;
st_a += sz;
}
if(b%2){
b--;
st_b -= sz;
fixed[b]=1;
fixval[b]=val;
sum[b] = sz * val;
mn[b] = val;
mnind[b] = st_b;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline void add(int a, int b, T val){
int sz = 1;
int aa;
int bb;
if(a >= b){
return;
}
aa = (a += N);
bb = (b += N);
push(a);
push(b-1);
if(a%2){
sum[a] += val;
mn[a] += val;
a++;
}
if(b%2){
b--;
sum[b] += val;
mn[b] += val;
}
a /= 2;
b /= 2;
while(a < b){
sz *= 2;
if(a%2){
if(fixed[a]){
fixval[a] += val;
}
else{
addval[a] += val;
}
sum[a] += sz * val;
mn[a] += val;
a++;
}
if(b%2){
b--;
if(fixed[b]){
fixval[b] += val;
}
else{
addval[b] += val;
}
sum[b] += sz * val;
mn[b] += val;
}
a /= 2;
b /= 2;
}
build(aa);
build(bb-1);
}
inline pair<T,int> getMin(int a, int b){
pair<T,int> res;
pair<T,int> tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res =min_L(res, make_pair(mn[a], mnind[a]));
}
else{
res = make_pair(mn[a], mnind[a]);
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp =min_L(make_pair(mn[b], mnind[b]), tmp);
}
else{
tmp = make_pair(mn[b], mnind[b]);
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res =min_L(res, tmp);
return res;
}
return res;
}
inline T getMinVal(int a, int b){
T res;
T tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res =min_L(res, mn[a]);
}
else{
res = mn[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp =min_L(mn[b], tmp);
}
else{
tmp = mn[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res =min_L(res, tmp);
return res;
}
return res;
}
inline int getMinInd(int a, int b){
return getMin(a,b).second;
}
inline T getSum(int a, int b){
T res;
T tmp;
int fga = 0;
int fgb = 0;
a += N;
b += N;
push(a);
push(b-1);
while(a < b){
if(a%2){
if(fga){
res = res + sum[a];
}
else{
res = sum[a];
fga = 1;
}
a++;
}
if(b%2){
b--;
if(fgb){
tmp = sum[b] + tmp;
}
else{
tmp = sum[b];
fgb = 1;
}
}
a /= 2;
b /= 2;
}
if(fga==1 && fgb==0){
return res;
}
if(fga==0 && fgb==1){
return tmp;
}
if(fga==1 && fgb==1){
res = res + tmp;
return res;
}
return res;
}
}
;
struct graph{
int N;
int*es;
int**edge;
void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
int i;
N = N__;
walloc1d(&es, N, mem);
walloc1d(&edge, N, mem);
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
es[A[i]]++;
es[B[i]]++;
}
for(i=(0);i<(N);i++){
walloc1d(&edge[i], es[i], mem);
}
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
edge[A[i]][es[A[i]]++] = B[i];
edge[B[i]][es[B[i]]++] = A[i];
}
}
void getDist(int root, int res[], void *mem = wmem){
int i;
int j;
int k;
int*q;
int s;
int z;
walloc1d(&q, N, &mem);
for(i=(0);i<(N);i++){
res[i]=-1;
}
res[root]=0;
s=0;
z=1;
q[0]=root;
while(z){
i=q[s++];
z--;
for(j=(0);j<(es[i]);j++){
k=edge[i][j];
if(res[k]>=0){
continue;
}
res[k]=res[i]+1;
q[s+z++]=k;
}
}
}
int getDist(int a, int b, void *mem = wmem){
int i;
int j;
int k;
int*q;
int s;
int z;
int*d;
if(a==b){
return 0;
}
walloc1d(&d, N, &mem);
walloc1d(&q, N, &mem);
for(i=(0);i<(N);i++){
d[i] = -1;
}
d[a] = 0;
s = 0;
z = 1;
q[0] = a;
while(z){
i = q[s++];
z--;
for(j=(0);j<(es[i]);j++){
k = edge[i][j];
if(d[k] >= 0){
continue;
}
d[k] = d[i] + 1;
if(k==b){
return d[k];
}
q[s+z++] = k;
}
}
return -1;
}
}
;
template<class T> struct wgraph{
int N;
int*es;
int**edge;
T**cost;
graph g;
void setEdge(int N__, int M, int A[], int B[], T C[], void **mem = &wmem){
int i;
N = N__;
walloc1d(&es, N, mem);
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
es[A[i]]++;
es[B[i]]++;
}
walloc1d(&edge, N, mem);
for(i=(0);i<(N);i++){
walloc1d(&edge[i], es[i], mem);
}
walloc1d(&cost, N, mem);
for(i=(0);i<(N);i++){
walloc1d(&cost[i], es[i], mem);
}
for(i=(0);i<(N);i++){
es[i] = 0;
}
for(i=(0);i<(M);i++){
edge[A[i]][es[A[i]]] = B[i];
edge[B[i]][es[B[i]]] = A[i];
cost[A[i]][es[A[i]]++] = C[i];
cost[B[i]][es[B[i]]++] = C[i];
}
g.N = N;
g.es = es;
g.edge = edge;
}
template<class S> void getDist(int root, S res[], S unreachable = -1, void *mem = wmem){
int i;
int j;
DijkstraHeap<S> hp;
hp.walloc(N, &mem);
hp.init(N);
hp.change(root,0);
while(hp.size){
i = hp.pop();
for(j=(0);j<(es[i]);j++){
hp.change(edge[i][j], hp.val[i]+cost[i][j]);
}
}
for(i=(0);i<(N);i++){
res[i] = (hp.visited[i] ? hp.val[i] : unreachable);
}
}
}
;
struct HLD{
int N;
int*es;
int**edge;
int*group;
int*groupind;
int groupNum;
int*groupSize;
int**groupNode;
int*groupUpNode;
int*groupDepth;
void init(graph g, void **mem = &wmem){
init(g.N, g.es, g.edge, mem);
}
void init(int N__, int *es__, int **edge__, void **mem = &wmem){
int i;
int j;
int k;
int x;
int y;
int mx;
int*q;
int q_st;
int q_ed;
int*sz;
char*vis;
void*tmpmem;
N = N__;
es = es__;
edge = edge__;
walloc1d(&group, N, mem);
walloc1d(&groupind, N, mem);
tmpmem = *mem;
walloc1d(&q, N, &tmpmem);
walloc1d(&sz, N, &tmpmem);
walloc1d(&vis, N, &tmpmem);
for(i=(0);i<(N);i++){
vis[i] = 0;
}
q_st = 0;
q_ed = 1;
q[0] = 0;
vis[0] = 1;
while(q_st < q_ed){
i = q[q_st++];
for(j=(0);j<(es[i]);j++){
k = edge[i][j];
if(!vis[k]){
vis[k] = 1;
q[q_ed++] = k;
}
}
}
for(i=(0);i<(N);i++){
sz[i] = 0;
}
for(j=N-1;j>=0;j--){
i = q[j];
sz[i] = 1;
for(k=(0);k<(es[i]);k++){
sz[i] += sz[edge[i][k]];
}
}
for(i=(0);i<(N);i++){
group[i] = -1;
}
groupNum = 0;
for(j=(0);j<(N);j++){
i = q[j];
if(group[i]>=0){
continue;
}
group[i] = groupNum++;
groupind[i] = 0;
for(;;){
mx = -1;
for(k=(0);k<(es[i]);k++){
if(group[edge[i][k]] != -1){
continue;
}
if(mx==-1){
mx = k;
}
else if(sz[edge[i][k]] > sz[edge[i][mx]]){
mx = k;
}
}
if(mx==-1){
break;
}
group[edge[i][mx]] = group[i];
groupind[edge[i][mx]] = groupind[i]+1;
i = edge[i][mx];
}
}
walloc1d(&groupSize, groupNum, mem);
walloc1d(&groupUpNode, groupNum, mem);
walloc1d(&groupDepth, groupNum, mem);
for(i=(0);i<(groupNum);i++){
groupSize[i] = 0;
}
for(i=(0);i<(N);i++){
groupSize[group[i]]++;
}
walloc1d(&groupNode, groupNum, mem);
for(i=(0);i<(groupNum);i++){
walloc1d(&groupNode[i], groupSize[i], mem);
}
for(i=(0);i<(N);i++){
groupNode[group[i]][groupind[i]] = i;
}
for(i=(0);i<(groupNum);i++){
groupDepth[i] = -1;
}
groupUpNode[0] = -1;
groupDepth[0] = 0;
for(x=(0);x<(groupNum);x++){
for(y=(0);y<(groupSize[x]);y++){
i = groupNode[x][y];
for(j=(0);j<(es[i]);j++){
k = edge[i][j];
if(x != group[k] && groupDepth[group[k]]==-1){
groupUpNode[group[k]] = i;
groupDepth[group[k]] = groupDepth[x] + 1;
}
}
}
}
}
int lca(int x, int y){
int x1;
int y1;
int x2;
int y2;
x1 = group[x];
x2 = groupind[x];
y1 = group[y];
y2 = groupind[y];
while(groupDepth[x1] > groupDepth[y1]){
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
while(groupDepth[x1] < groupDepth[y1]){
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
while(x1 != y1){
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
if(x2 <= y2){
return x;
}
return y;
}
int depth(int x){
int x1;
int x2;
int res = 0;
x1 = group[x];
x2 = groupind[x];
while(groupUpNode[x1] != -1){
res += x2 + 1;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
return res + x2;
}
int dist(int x, int y){
int x1;
int y1;
int x2;
int y2;
int res = 0;
x1 = group[x];
x2 = groupind[x];
y1 = group[y];
y2 = groupind[y];
while(groupDepth[x1] > groupDepth[y1]){
res += x2 + 1;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
while(groupDepth[x1] < groupDepth[y1]){
res += y2 + 1;
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
while(x1 != y1){
res += x2 + y2 + 2;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
y = groupUpNode[y1];
y1 = group[y];
y2 = groupind[y];
}
if(x2 <= y2){
return res + y2 - x2;
}
return res + x2 - y2;
}
int up(int x){
int x1 = group[x];
int x2 = groupind[x];
if(x2==0){
return groupUpNode[x1];
}
return groupNode[x1][x2-1];
}
int up(int x, int d){
int x1 = group[x];
int x2 = groupind[x];
while(d > x2){
if(groupUpNode[x1]==-1){
return -1;
}
d -= x2 + 1;
x = groupUpNode[x1];
x1 = group[x];
x2 = groupind[x];
}
return groupNode[x1][x2-d];
}
}
;
template<class T> struct HLD_segtree{
HLD*hld;
segtree<T>*seg;
void init(HLD *hld__, T initval[], void **mem = &wmem){
int i;
int j;
hld = hld__;
walloc1d(&seg, hld->groupNum, mem);
for(i=(0);i<(hld->groupNum);i++){
seg[i].walloc(hld->groupSize[i], 0, mem);
seg[i].setN(hld->groupSize[i], 0, 0);
if(initval!=NULL){
for(j=(0);j<(hld->groupSize[i]);j++){
seg[i][j] = initval[ hld->groupNode[i][j] ];
}
}
else{
for(j=(0);j<(hld->groupSize[i]);j++){
seg[i][j] = 0;
}
}
seg[i].build();
}
}
inline void change(int u, int v, T val){
int ug;
int vg;
int ui;
int vi;
ug = hld->group[u];
vg = hld->group[v];
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
seg[ug].change(0, hld->groupind[u]+1, val);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
seg[ug].change(min_L(ui, vi),max_L(ui, vi)+1, val);
}
inline void add(int u, int v, T val){
int ug;
int vg;
int ui;
int vi;
ug = hld->group[u];
vg = hld->group[v];
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
seg[ug].add(0, hld->groupind[u]+1, val);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
seg[ug].add(min_L(ui, vi),max_L(ui, vi)+1, val);
}
inline pair<T,int> getMin(int u, int v){
pair<T,int> res;
pair<T,int> tmp;
int ug;
int vg;
int ui;
int vi;
ug = hld->group[u];
vg = hld->group[v];
res.first = numeric_limits<T>::max();
res.second = -1;
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
tmp = seg[ug].getMin(0, hld->groupind[u]+1);
tmp.second = hld->groupNode[ug][tmp.second];
chmin(res, tmp);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
tmp = seg[ug].getMin(min_L(ui, vi),max_L(ui, vi)+1);
tmp.second = hld->groupNode[ug][tmp.second];
chmin(res, tmp);
return res;
}
inline T getMinVal(int u, int v){
return getMin(u,v).first;
}
inline int getMinInd(int u, int v){
return getMin(u,v).second;
}
inline T getSum(int u, int v){
T res;
int ug;
int vg;
int ui;
int vi;
ug = hld->group[u];
vg = hld->group[v];
res = 0;
while(ug != vg){
if(hld->groupDepth[ug] < hld->groupDepth[vg]){
swap(u, v);
swap(ug, vg);
}
res += seg[ug].getSum(0, hld->groupind[u]+1);
u = hld->groupUpNode[ug];
ug = hld->group[u];
}
ui = hld->groupind[u];
vi = hld->groupind[v];
res += seg[ug].getSum(min_L(ui, vi),max_L(ui, vi)+1);
return res;
}
inline void change_edge(int u, int v, T val){
int x;
int z;
int d;
z = hld->lca(u, v);
d = hld->depth(z);
if(z != u){
x = hld->up(u, hld->depth(u) - d - 1);
change(u, x, val);
}
if(z != v){
x = hld->up(v, hld->depth(v) - d - 1);
change(v, x, val);
}
}
inline void add_edge(int u, int v, T val){
int x;
int z;
int d;
z = hld->lca(u, v);
d = hld->depth(z);
if(z != u){
x = hld->up(u, hld->depth(u) - d - 1);
add(u, x, val);
}
if(z != v){
x = hld->up(v, hld->depth(v) - d - 1);
add(v, x, val);
}
}
inline pair<T,int> getMin_edge(int u, int v){
int x;
int z;
int d;
pair<T,int> res;
pair<T,int> tmp;
res.first = numeric_limits<T>::max();
res.second = -1;
z = hld->lca(u, v);
d = hld->depth(z);
if(z != u){
x = hld->up(u, hld->depth(u) - d - 1);
tmp = getMin(u, x);
chmin(res, tmp);
}
if(z != v){
x = hld->up(v, hld->depth(v) - d - 1);
tmp = getMin(v, x);
chmin(res, tmp);
}
return res;
}
inline T getMinVal_edge(int u, int v){
return getMin_edge(u,v).first;
}
inline int getMinInd_edge(int u, int v){
return getMin_edge(u,v).second;
}
inline T getSum_edge(int u, int v){
int x;
int z;
int d;
T res;
res = 0;
z = hld->lca(u, v);
d = hld->depth(z);
if(z != u){
x = hld->up(u, hld->depth(u) - d - 1);
res += getSum(u, x);
}
if(z != v){
x = hld->up(v, hld->depth(v) - d - 1);
res += getSum(v, x);
}
return res;
}
}
;
int N;
int K;
int A[300000];
int B[300000];
int M[10];
int X[10][100000];
int U;
int V;
long long C[300000];
long long P[10];
wgraph<long long> g;
HLD hld;
HLD_segtree<long long> t;
long long di[10][100000+20];
long long db[10][10];
int main(){
int aTqQ6rt8;
wmem = memarr;
int i;
int j;
int k;
int m;
void*mem;
rd(N);
rd(K);
{
int Lj4PdHRW;
for(Lj4PdHRW=(0);Lj4PdHRW<(N-1);Lj4PdHRW++){
rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1);
rd(B[Lj4PdHRW]);B[Lj4PdHRW] += (-1);
rd(C[Lj4PdHRW]);
}
}
for(i=(0);i<(K);i++){
rd(M[i]);
rd(P[i]);
{
int RZTsC2BF;
for(RZTsC2BF=(0);RZTsC2BF<(M[i]);RZTsC2BF++){
rd(X[i][RZTsC2BF]);X[i][RZTsC2BF] += (-1);
}
}
}
for(k=(0);k<(K);k++){
m = N-1;
for(i=(0);i<(M[k]);i++){
arrInsert(m, m, A, N, B, X[k][i], C, 0LL);
}
mem = wmem;
g.setEdge(N+1, m, A, B, C);
g.getDist(N, di[k]);
wmem = mem;
}
for(i=(0);i<(K);i++){
for(j=(0);j<(K);j++){
db[i][j] = 4611686016279904256LL;
}
}
for(i=(0);i<(K);i++){
db[i][i] = P[i];
}
for(i=(0);i<(K);i++){
for(j=(0);j<(K);j++){
for(k=(0);k<(M[j]);k++){
chmin(db[i][j], di[i][X[j][k]] + P[i] + P[j]);
}
}
}
for(k=(0);k<(K);k++){
for(i=(0);i<(K);i++){
for(j=(0);j<(K);j++){
chmin(db[i][j], db[i][k] + db[k][j] - P[k]);
}
}
}
g.setEdge(N, N-1, A, B, C);
hld.init(g.g);
t.init(&hld, NULL);
for(i=(0);i<(N-1);i++){
j = hld.depth(A[i]);
k = hld.depth(B[i]);
if(j > k){
t.change(A[i], A[i], C[i]);
}
if(j < k){
t.change(B[i], B[i], C[i]);
}
}
int X9Iss0pP = rd_int();
for(aTqQ6rt8=(0);aTqQ6rt8<(X9Iss0pP);aTqQ6rt8++){
long long res = 4611686016279904256LL;
rd(U);U += (-1);
rd(V);V += (-1);
chmin(res, t.getSum_edge(U, V));
for(i=(0);i<(K);i++){
for(j=(0);j<(K);j++){
chmin(res, db[i][j] + di[i][U] + di[j][V]);
}
}
wt_L(res);
wt_L('\n');
}
return 0;
}
// cLay version 20210321-1 [beta]
// --- original code ---
// int N, K, A[3d5], B[3d5], M[10], X[10][1d5], U, V;
// ll C[3d5], P[10];
// wgraph<ll> g;
// HLD hld;
// HLD_segtree<ll> t;
// ll di[10][1d5+20], db[10][10];
// {
// int i, j, k, m;
// void *mem;
// rd(N,K,(A--,B--,C)(N-1));
// rep(i,K) rd(M[i], P[i], (X[i]--)(M[i]));
//
// rep(k,K){
// m = N-1;
// rep(i,M[k]) arrInsert(m, m, A, N, B, X[k][i], C, 0LL);
// mem = wmem;
// g.setEdge(N+1, m, A, B, C);
// g.getDist(N, di[k]);
// wmem = mem;
// }
//
// rep(i,K) rep(j,K) db[i][j] = ll_inf;
// rep(i,K) db[i][i] = P[i];
// rep(i,K) rep(j,K) rep(k,M[j]) db[i][j] <?= di[i][X[j][k]] + P[i] + P[j];
// rep(k,K) rep(i,K) rep(j,K) db[i][j] <?= db[i][k] + db[k][j] - P[k];
//
// g.setEdge(N, N-1, A, B, C);
// hld.init(g.g);
// t.init(&hld, NULL);
// rep(i,N-1){
// j = hld.depth(A[i]);
// k = hld.depth(B[i]);
// if(j > k) t.change(A[i], A[i], C[i]);
// if(j < k) t.change(B[i], B[i], C[i]);
// }
//
// REP(rd_int()){
// ll res = ll_inf;
// rd(U--, V--);
// res <?= t.getSum_edge(U, V);
// rep(i,K) rep(j,K) res <?= db[i][j] + di[i][U] + di[j][V];
// wt(res);
// }
// }