#ifdef _MSC_VER #define _CRT_SECURE_NO_WARNINGS #endif #include<iostream> #include<cstdio> #include<algorithm> #include<utility> #include<set> #include<map> #include<queue> #include<vector> #include<string> //code by cl3488 #define RI(X) scanf("%d", &(X)) #define RII(X, Y) scanf("%d%d", &(X), &(Y)) #define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z)) #define DRI(X) int (X); scanf("%d", &X) #define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y) #define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z) #define println(X) printf("%d\n",(X)) #define PB push_back #define MP make_pair #define mid ((L + R)>>1) typedef long long ll; using namespace std; typedef pair<int, int> pii; const int INF = (int)1e9; const int MAXN = 100005; ll wsum[30 * MAXN];//static once the tree is built. ll dot[30 * MAXN]; int pending[30 * MAXN]; bool zero[30 * MAXN]; int ch[30 * MAXN][2]; int tt = 0;//0 is a dumping ground for all leaves. ll ans = 0; int N; int M; void access(int p){ if (zero[p]){ pending[p] = 0; dot[p] = 0; zero[ch[p][0]] = true; zero[ch[p][1]] = true; zero[p] = false; } for (int c = 0; c < 2; c++){ int q = ch[p][c]; if (zero[q]){ pending[q] = 0; dot[q] = 0; zero[ch[q][0]] = true; zero[ch[q][1]] = true; zero[q] = false; } } dot[p] += wsum[p] * pending[p]; pending[ch[p][0]] += pending[p]; pending[ch[p][1]] += pending[p]; pending[p] = 0; } void updata(int p, int L, int R, int i){ access(p); if (i >= R){ pending[p]++; access(p); return; } if (i < L) return; updata(ch[p][0], L, mid, i); updata(ch[p][1], mid + 1, R, i); dot[p] = dot[ch[p][0]] + dot[ch[p][1]]; } void suma(int p, int L, int R, int i){ access(p); if (i >= R){ ans -= 2 * dot[p]; return; } if (i < L) return; suma(ch[p][0], L, mid, i); suma(ch[p][1], mid + 1, R, i); } vector<int> weight; void buildTree(int L, int R){ tt++; int now = tt; if (L == R){ wsum[now] = weight[L]; return; } ch[now][0] = tt + 1; buildTree(L, mid); ch[now][1] = tt + 1; buildTree(mid + 1, R); wsum[now] = wsum[ch[now][0]] + wsum[ch[now][1]]; } struct ST { int n; int root; void init(int EN){ n = EN; root = tt + 1; buildTree(0, n-1); } void update(int i){ updata(root, 0, n-1, i); } void sum(int i){ suma(root, 0, n - 1, i); } void reset(){ ans = 0; zero[root] = true; } }; vector<pii> adj[MAXN]; int heavy[MAXN]; int pa[MAXN]; int sz[MAXN]; ll depth[MAXN]; int chain[MAXN]; int pinch[MAXN]; int lench[MAXN]; int head[MAXN]; ST atop[MAXN]; int weights[MAXN]; void dfs(int v){ sz[v] = 1; for (pii uu : adj[v]){ int u = uu.first; if (u == pa[v]) continue; pa[u] = v; depth[u] = depth[v] + uu.second; weights[u] = uu.second; dfs(u); sz[v] += sz[u]; } for (pii uu : adj[v]){ int u = uu.first; if (u == pa[v]) continue; if (sz[u] * 2 >= sz[v]){ heavy[v] = u; break; } } } vector<int> lightedges;//static list of light edges int light[MAXN];//for the light edges void perform(int a){ //sums then updates each edge from a to the root. while (a != 1){ if (a == head[chain[a]]){//light edge //cout << "We treat " << a << " as light.\n"; ans -= weights[a] * (2 * light[a]); light[a]++; a = pa[a]; continue; } int k = pinch[a]; //cout << k - 1 << " ! "; atop[chain[a]].sum(k - 1); atop[chain[a]].update(k - 1); a = head[chain[a]]; } } int main(){ //weight = vector<int>(); //weight.push_back(10); weight.push_back(40); weight.push_back(20); weight.push_back(80); weight.push_back(50); weight.push_back(70); //ST e; //e.init(weight.size()); //e.reset(); //e.sum(4); //e.update(4); //e.sum(3); //e.update(3); //cout << ans << "\n"; //freopen("input.txt", "r", stdin); cin >> N >> M; //if (N > 0) return 0; for (int e = 0; e < N - 1; e++){ int a; int b; int c; RIII(a, b, c); adj[a].push_back(pii(b, c)); adj[b].push_back(pii(a, c)); } int root = 1; dfs(root); int counter = 1; for (int u = 1; u <= N; u++){ if (heavy[pa[u]] == u){ continue; } lightedges.push_back(u); //cout << "We know that " << u << " is light.\n"; weight = vector<int>(); int place = 0; for (int i = u; i != 0; i = heavy[i]){ chain[i] = counter; pinch[i] = place; if (i != u){ weight.push_back(weights[i]); } place++; } lench[counter] = place; head[counter] = u; if(weight.size() != 0) atop[counter].init(weight.size()); counter++; } for (int query = 0; query < M; query++){ //reset everything for (int e : lightedges){ light[e] = 0; } for (int c = 1; c < counter; c++){ atop[c].reset(); } DRI(V); for (int i = 0; i < V; i++){ DRI(v); ans += (V - 1) * depth[v]; //cout << ans << " "; perform(v); //cout << ans << "!\n"; } cout << ans << "\n"; } return 0; }