結果
| 問題 | No.1212 Second Path |
| ユーザー |
 LayCurse
|
| 提出日時 | 2020-08-30 16:48:34 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 27,282 bytes |
| コンパイル時間 | 3,534 ms |
| コンパイル使用メモリ | 229,956 KB |
| 実行使用メモリ | 53,328 KB |
| 最終ジャッジ日時 | 2024-04-27 10:16:51 |
| 合計ジャッジ時間 | 17,108 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 157 ms
32,972 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | AC | 146 ms
35,480 KB |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | AC | 9 ms
10,200 KB |
| testcase_24 | WA | - |
| testcase_25 | AC | 15 ms
10,200 KB |
| testcase_26 | WA | - |
| testcase_27 | AC | 14 ms
11,848 KB |
| testcase_28 | AC | 13 ms
10,200 KB |
| testcase_29 | AC | 243 ms
35,508 KB |
| testcase_30 | AC | 224 ms
33,104 KB |
| testcase_31 | AC | 226 ms
33,100 KB |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
| testcase_40 | WA | - |
| testcase_41 | WA | - |
| testcase_42 | AC | 3 ms
9,808 KB |
| testcase_43 | AC | 4 ms
11,724 KB |
| testcase_44 | AC | 3 ms
9,676 KB |
| testcase_45 | AC | 91 ms
53,328 KB |
| testcase_46 | AC | 86 ms
51,784 KB |
| testcase_47 | AC | 91 ms
51,916 KB |
コンパイルメッセージ
main.cpp: In member function 'T HLD_segtree<T>::getSum(int, int) [with T = long long int]':
main.cpp:1151:9: warning: 'res' may be used uninitialized [-Wmaybe-uninitialized]
1151 | res += seg[ug].getSum(min_L(ui, vi),max_L(ui, vi)+1);
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:637:7: note: 'res' was declared here
637 | T res;
| ^~~
In member function 'T segtree<T>::getSum(int, int) [with T = long long int]',
inlined from 'T HLD_segtree<T>::getSum(int, int) [with T = long long int]' at main.cpp:1151:26:
main.cpp:676:11: warning: 'tmp' may be used uninitialized [-Wmaybe-uninitialized]
676 | res = res + tmp;
| ~~~~^~~~~~~~~~~
main.cpp: In member function 'T HLD_segtree<T>::getSum(int, int) [with T = long long int]':
main.cpp:638:7: note: 'tmp' was declared here
638 | T tmp;
| ^~~
main.cpp:1145:11: warning: 'res' may be used uninitialized [-Wmaybe-uninitialized]
1145 | res += seg[ug].getSum(0, hld->groupind[u]+1);
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:637:7: note: 'res' was declared here
637 | T res;
| ^~~
In member function 'T segtree<T>::getSum(int, int) [with T = long long int]',
inlined from 'T HLD_segtree<T>::getSum(int, int) [with T = long long int]' at main.cpp:1145:28:
main.cpp:676:11: warning: 'tmp' may be used uninitialized [-Wmaybe-uninitialized]
676 | res = res + tmp;
| ~~~~^~~~~~~~~~~
main.cpp: In member function 'T HLD_segtree<T>::getSum(int, int) [with T = long long int]':
main.cpp:638:7: note: 'tmp' was declared here
638 | 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);
}
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(int x){
int s=0;
int m=0;
char f[10];
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');
}
}
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, 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 Wu3kZ3t7 = N;
for(i=(1);i<(Wu3kZ3t7);i++){
fixed[i] = 0;
}
int grBCmONb = N;
for(i=(1);i<(grBCmONb);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;
}
}
}
}
;
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;
}
}
;
int N;
int A[100000];
int B[100000];
long long C[100000];
int X;
int Y;
wgraph<long long> g;
HLD hld;
HLD_segtree<long long> t;
HLD_segtree<long long> tdis;
int dep[100000];
long long mn1[100000];
long long mn2[100000];
long long mn3[100000];
long long mn[100000];
long long updis[100000];
long long cand[3];
int main(){
int a2conNHc, i;
wmem = memarr;
int xx;
int yy;
int xxx;
int yyy;
int z;
long long res;
long long ad;
rd(N);
{
int Lj4PdHRW;
for(Lj4PdHRW=(0);Lj4PdHRW<(N-1);Lj4PdHRW++){
rd(A[Lj4PdHRW]);A[Lj4PdHRW] += (-1);
rd(B[Lj4PdHRW]);B[Lj4PdHRW] += (-1);
rd(C[Lj4PdHRW]);
}
}
g.setEdge(N,N-1,A,B,C);
g.g.getDist(0, dep);
hld.init(g.g);
t.init(&hld, NULL);
tdis.init(&hld, NULL);
for(i=(0);i<(N);i++){
mn[i] = mn1[i] = mn2[i] = mn3[i] = updis[i] = 4611686016279904256LL;
}
for(i=(0);i<(N-1);i++){
if(dep[A[i]] > dep[B[i]]){
swap(A[i], B[i]);
}
chmin(mn3[A[i]], C[i]);
if(mn1[A[i]] > mn2[A[i]]){
swap(mn1[A[i]], mn2[A[i]]);
}
if(mn2[A[i]] > mn3[A[i]]){
swap(mn2[A[i]], mn3[A[i]]);
}
if(mn1[A[i]] > mn2[A[i]]){
swap(mn1[A[i]], mn2[A[i]]);
}
;
updis[B[i]] = C[i];
}
for(i=(0);i<(N-1);i++){
if(mn1[A[i]] != C[i]){
mn[B[i]] =mn1[A[i]];
}
else{
mn[B[i]] =mn2[A[i]];
}
}
for(i=(0);i<(N);i++){
t.change(i,i,mn[i]);
}
for(i=(0);i<(N-1);i++){
tdis.change(B[i],B[i],C[i]);
}
int hCmBdyQB = rd_int();
for(a2conNHc=(0);a2conNHc<(hCmBdyQB);a2conNHc++){
rd(X);X += (-1);
rd(Y);Y += (-1);
z = hld.lca(X, Y);
res = 0;
ad = 4611686016279904256LL;
xx = yy = xxx = yyy = -1;
if(X != z){
xx = hld.up(X, dep[X] - dep[z] - 1);
}
if(Y != z){
yy = hld.up(Y, dep[Y] - dep[z] - 1);
}
if(xx != -1 && xx != X){
xxx = hld.up(dep[X] - dep[z] - 2);
}
if(yy != -1 && yy != Y){
yyy = hld.up(dep[Y] - dep[z] - 2);
}
if(xx != -1){
res += tdis.getSum(X, xx);
}
if(yy != -1){
res += tdis.getSum(Y, yy);
}
chmin(ad, updis[z]);
if(xx != -1){
chmin(ad, mn1[X]);
}
if(yy != -1){
chmin(ad, mn1[Y]);
}
if(xxx != -1){
chmin(ad, t.getMinVal(X, xxx));
}
if(yyy != -1){
chmin(ad, t.getMinVal(Y, yyy));
}
cand[0] = mn1[z];
cand[1] = mn2[z];
cand[2] = mn3[z];
if(xx != -1){
for(i=(0);i<(3);i++){
if(cand[i]==updis[xx]){
cand[i] = 4611686016279904256LL;
break;
}
}
}
if(yy != -1){
for(i=(0);i<(3);i++){
if(cand[i]==updis[yy]){
cand[i] = 4611686016279904256LL;
break;
}
}
}
{
int iMWUTgY_;
long long AlM5nNnR;
if(3==0){
AlM5nNnR = 0;
}
else{
AlM5nNnR = cand[0];
for(iMWUTgY_=(1);iMWUTgY_<(3);iMWUTgY_++){
AlM5nNnR = min_L(AlM5nNnR, cand[iMWUTgY_]);
}
}
chmin(ad, AlM5nNnR);
}
if(ad == 4611686016279904256LL){
wt_L(-1);
wt_L('\n');
continue;
}
wt_L(res + ad * 2);
wt_L('\n');
}
return 0;
}
// cLay varsion 20200813-1 [beta]
// --- original code ---
// int N, A[1d5], B[1d5]; ll C[1d5];
// int X, Y;
//
// wgraph<ll> g;
// HLD hld;
// HLD_segtree<ll> t, tdis;
// int dep[1d5];
// ll mn1[1d5], mn2[1d5], mn3[1d5], mn[1d5], updis[1d5];
// ll cand[3];
//
// {
// int xx, yy, xxx, yyy, z;
// ll res, ad;
// rd(N,(A--,B--,C)(N-1));
//
// g.setEdge(N,N-1,A,B,C);
// g.g.getDist(0, dep);
// hld.init(g.g);
// t.init(&hld, NULL);
// tdis.init(&hld, NULL);
//
// rep(i,N) mn[i] = mn1[i] = mn2[i] = mn3[i] = updis[i] = ll_inf;
// rep(i,N-1){
// if(dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
// mn3[A[i]] <?= C[i];
// sortE(mn1[A[i]], mn2[A[i]], mn3[A[i]]);
// updis[B[i]] = C[i];
// }
// rep(i,N-1) mn[B[i]] = if[mn1[A[i]] != C[i], mn1[A[i]], mn2[A[i]]];
// rep(i,N) t.change(i,i,mn[i]);
// rep(i,N-1) tdis.change(B[i],B[i],C[i]);
//
// REP(rd_int()){
// rd(X--, Y--);
// z = hld.lca(X, Y);
//
// res = 0;
// ad = ll_inf;
// xx = yy = xxx = yyy = -1;
//
// if(X != z) xx = hld.up(X, dep[X] - dep[z] - 1);
// if(Y != z) yy = hld.up(Y, dep[Y] - dep[z] - 1);
// if(xx != -1 && xx != X) xxx = hld.up(dep[X] - dep[z] - 2);
// if(yy != -1 && yy != Y) yyy = hld.up(dep[Y] - dep[z] - 2);
//
// // wt(z,":",X,xxx,xx,":",Y,yyy,yy);
//
// if(xx != -1) res += tdis.getSum(X, xx);
// if(yy != -1) res += tdis.getSum(Y, yy);
//
// ad <?= updis[z];
// if(xx != -1) ad <?= mn1[X];
// if(yy != -1) ad <?= mn1[Y];
// if(xxx != -1) ad <?= t.getMinVal(X, xxx);
// if(yyy != -1) ad <?= t.getMinVal(Y, yyy);
//
// cand[0] = mn1[z];
// cand[1] = mn2[z];
// cand[2] = mn3[z];
// if(xx != -1) rep(i,3) if(cand[i]==updis[xx]) cand[i] = ll_inf, break;
// if(yy != -1) rep(i,3) if(cand[i]==updis[yy]) cand[i] = ll_inf, break;
// ad <?= min(cand(3));
//
// if(ad == ll_inf) wt(-1), continue;
// wt(res + ad * 2);
// }
// }