結果
問題 | No.1212 Second Path |
ユーザー |
![]() |
提出日時 | 2020-08-30 16:58:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 444 ms / 3,000 ms |
コード長 | 27,294 bytes |
コンパイル時間 | 3,992 ms |
コンパイル使用メモリ | 229,492 KB |
最終ジャッジ日時 | 2025-01-14 00:21:28 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 45 |
コンパイルメッセージ
main.cpp: In member function ‘T HLD_segtree<T>::getSum(int, int) [with T = long long int]’: 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; | ^~~ 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; | ^~~
ソースコード
#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(X, dep[X] - dep[z] - 2);}if(yy != -1 && yy != Y){yyy = hld.up(Y, 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(X, dep[X] - dep[z] - 2);// if(yy != -1 && yy != Y) yyy = hld.up(Y, 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);// }// }