結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 21:55:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 115 ms / 4,000 ms |
コード長 | 12,944 bytes |
コンパイル時間 | 3,290 ms |
コンパイル使用メモリ | 228,508 KB |
最終ジャッジ日時 | 2025-01-07 20:30:05 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
ソースコード
#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 T1> void sortA_L(int N, T1 a[], void *mem = wmem){sort(a, a+N);}template<class T1, class T2> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){int i;pair<T1, T2> *arr;walloc1d(&arr, N, &mem);for(i=(0);i<(N);i++){arr[i].first = a[i];arr[i].second = b[i];}sort(arr, arr+N);for(i=(0);i<(N);i++){a[i] = arr[i].first;b[i] = arr[i].second;}}inline void rd(int &x){int k;int m=0;x=0;for(;;){k = getchar_unlocked();if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){k = 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;}inline void wt_L(char a){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){putchar_unlocked('-');}while(s--){putchar_unlocked(f[s]+'0');}}template<class T> struct fenwick{int size;int memory;T *data;void malloc(int mem){memory = mem;data = (T*)std::malloc(sizeof(T)*mem);}void walloc(int mem, void **workMemory=&wmem){memory = mem;walloc1d(&data, mem, workMemory);}void free(void){memory = 0;free(data);}void init(int N){size = N;memset(data,0,sizeof(T)*N);}void add(int k, T val){while(k < size){data[k] += val;k |= k+1;}}T get(int k){T res = 0;while(k>=0){res += data[k];k = (k&(k+1))-1;}return res;}T range(int a, int b){if(b==-1){b=size-1;}return get(b) - get(a-1);}int kth(T k){int i=0;int j=size;int c;T v;while(i<j){c = (i+j)/2;v = get(c);if(v <= k){i=c+1;}else{j=c;}}return i==size?-1:i;}};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 preorder(int res[], int root = 0, void *mem=wmem){int i;int j;int k;int *st;int sts;int sz = 0;char *vis;walloc1d(&vis, N, &mem);walloc1d(&st, N, &mem);sts = 0;st[sts++] = root;for(i=(0);i<(N);i++){vis[i] = 0;}vis[root] = 1;while(sts){i = st[--sts];res[sz++] = i;for(j=(0);j<(es[i]);j++){k = edge[i][j];if(vis[k]){continue;}vis[k] = 1;st[sts++] = k;}}return sz;}};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_fenwick{HLD *hld;fenwick<T> *fen;void init(HLD *hld__, void **mem = &wmem){int i;int j;hld = hld__;walloc1d(&fen, hld->groupNum, mem);for(i=(0);i<(hld->groupNum);i++){fen[i].walloc(hld->groupSize[i], mem);fen[i].init(hld->groupSize[i]);}}inline void add(int u, T val){int ug;int ui;ug = hld->group[u];ui = hld->groupind[u];fen[ug].add(ui, val);}inline T get(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 += fen[ug].get(hld->groupind[u]);u = hld->groupUpNode[ug];ug = hld->group[u];}ui = hld->groupind[u];vi = hld->groupind[v];res += fen[ug].range(min_L(ui, vi),max_L(ui, vi));return res;}};int N;int A[100000];int B[100000];int C[100000];int sz;int X[3];int dis[100001];int pre[100000];int val[100000];int main(){int KL2GvlyY;wmem = memarr;int i;int j;int k;long long res;graph g;HLD hld;HLD_fenwick<long long> t;rd(N);{int Lj4PdHRW;for(Lj4PdHRW=(0);Lj4PdHRW<(N-1);Lj4PdHRW++){rd(A[Lj4PdHRW]);rd(B[Lj4PdHRW]);rd(C[Lj4PdHRW]);}}g.setEdge(N,N-1,A,B);hld.init(g);t.init(&hld);g.getDist(0,dis);dis[N] = -1073709056;for(i=(0);i<(N-1);i++){if(dis[A[i]] > dis[B[i]]){swap(A[i], B[i]);}}for(i=(0);i<(N-1);i++){t.add(B[i], C[i]);}g.preorder(val);for(i=(0);i<(N);i++){pre[val[i]] = i;}int Q5VJL1cS = rd_int();for(KL2GvlyY=(0);KL2GvlyY<(Q5VJL1cS);KL2GvlyY++){sz = 3;{int e98WHCEY;for(e98WHCEY=(0);e98WHCEY<(sz);e98WHCEY++){rd(X[e98WHCEY]);}}for(i=(0);i<(sz);i++){val[i] = pre[X[i]];}sortA_L(sz, val, X);res = 0;while(sz > 1){if(sz==2){i =N;}else{i =hld.lca(X[sz-3], X[sz-2]);}j = hld.lca(X[sz-2], X[sz-1]);if(dis[i] < dis[j]){if(j != X[sz-2]){res += t.get(j, X[sz-2]) - t.get(j,j);}if(j != X[sz-1]){res += t.get(j, X[sz-1]) - t.get(j,j);}X[sz-2] = j;}else{if(i != X[sz-3]){res += t.get(i, X[sz-3]) - t.get(i,i);}if(i != X[sz-2]){res += t.get(i, X[sz-2]) - t.get(i,i);}if(sz != 2){X[sz-3] = X[sz-1];}X[sz-2] = i;}sz--;}wt_L(res);wt_L('\n');}return 0;}// cLay varsion 20190929-1// --- original code ---// int N, A[1d5], B[1d5], C[1d5];// int sz, X[3];// int dis[100001], pre[1d5], val[1d5];// {// int i, j, k;// ll res;// graph g;// HLD hld;// HLD_fenwick<ll> t;// rd(N,(A,B,C)(N-1));//// g.setEdge(N,N-1,A,B);// hld.init(g);// t.init(&hld);//// g.getDist(0,dis);// dis[N] = -int_inf;// rep(i,N-1) if(dis[A[i]] > dis[B[i]]) swap(A[i], B[i]);// rep(i,N-1) t.add(B[i], C[i]);//// g.preorder(val);// rep(i,N) pre[val[i]] = i;//// REP(rd_int()){// sz = 3;// rd(X(sz));// rep(i,sz) val[i] = pre[X[i]];// sortA(sz, val, X);// res = 0;// while(sz > 1){// i = if[sz==2, N, hld.lca(X[sz-3], X[sz-2])];// j = hld.lca(X[sz-2], X[sz-1]);// if(dis[i] < dis[j]){// if(j != X[sz-2]) res += t.get(j, X[sz-2]) - t.get(j,j);// if(j != X[sz-1]) res += t.get(j, X[sz-1]) - t.get(j,j);// X[sz-2] = j;// } else {// if(i != X[sz-3]) res += t.get(i, X[sz-3]) - t.get(i,i);// if(i != X[sz-2]) res += t.get(i, X[sz-2]) - t.get(i,i);// if(sz != 2) X[sz-3] = X[sz-1];// X[sz-2] = i;// }// sz--;// }// wt(res);// }// }