- #include
- #include
- #include
- #include
- #include <string>
- #include
- #include
- #include
- #include
- #include <set>
- #include
- #include
- #include
- #defineeps 1e-7#defineINF 0x3f3f3f3f#defineMOD 1000000007#definerep0(j,n) for(int j=0;j#definerep1(j,n) for(int j=1;j<=n;++j)#definepb push_back#defineset0(n) memset(n,0,sizeof(n))#definell long long#defineull unsigned long long#defineiter(i,v) for(edge *i=head[v];i;i=i->nxt)#definemax(a,b) (a>b?a:b)#definemin(a,b) (a#defineprint_runtime printf("Running time:%.3lfs\n",double(clock())/1000.0)#defineTO(j) printf(#j": %d\n",j);//#define OJ
- using namespace std;
- const intMAXINT =250010;
- const intMAXNODE =100010;
- const intMAXEDGE =2* MAXNODE;
- charBUF[30000000], *buf;
- int read() {
- intx =0;
- while(!isdigit(*buf)) buf++;
- while(isdigit(*buf)) { x = x *10+ *buf++ -'0';}
- return x;
- }
- //------------------- Head Files ----------------------//
- int toid[MAXINT];
- struct res {
- int v, p;
- res(int_v,int _p) : v(_v), p(_p) {}
- res() {}
- };
- res add(res a, res b) {
- return(a.v < b.v a : b);
- }
- struct node {
- int lb, rb;
- node *l, *r;
- res ans, org;
- int del, cv, rec;
- inline voidrecover() __attribute__((optimize("-O2"))){
- del =0;
- cv = INF;
- ans = org;
- rec =1;
- }
- inline voidcover(intc) __attribute__((optimize("-O2"))){
- cv = ans.v = c;
- if(del) del =0;
- }
- inline voiddec(intc) __attribute__((optimize("-O2"))){
- del += c;
- ans.v -= c;
- }
- inline voidpushdown() __attribute__((optimize("-O2"))){
- if (rec) {
- l->recover(); r->recover();
- rec =0;
- }
- if(cv != INF) {
- l->cover(cv); r->cover(cv);
- cv = INF;
- }
- if(del !=0) {
- l->dec(del);
- r->dec(del);
- del =0;
- }
- }
- inline voidpushup() __attribute__((optimize("-O2"))){
- ans = add(l->ans, r->ans);
- }
- node() {
- ans.v = del = cv = INF;
- rec =0;
- }
- };
- intn, m, fa[MAXINT], sz[MAXINT], top[MAXINT], dfn[MAXINT], cnt_dfn =1, dep[MAXINT], cnt, va[MAXINT], val[MAXINT], dfne[MAXINT];
- struct SegTree {
- node mp[MAXINT *4];
- node *root;
- int _cnt;
- SegTree() {
- _cnt =0;
- }
- inline node *newnode(intl,intr) __attribute__((optimize("-O2"))){
- node *p = &mp[_cnt++];
- p->lb = l;
- p->rb = r;
- return p;
- }
- inline voidmaketree(intlb,intrb, node *&p) __attribute__((optimize("-O2"))){
- p = newnode(lb, rb);
- if(rb - lb >1) {
- maketree(lb, (lb + rb) /2, p->l);
- maketree((lb + rb) /2, rb, p->r);
- p->pushup();
- }
- else {
- p->ans.v = val[p->lb];
- p->ans.p = lb;
- }
- p->org = p->ans;
- }
- inline voiddel(intlb,intrb,intc) __attribute__((optimize("-O2"))){
- del(lb, rb, c, root);
- }
- inline voiddel(intlb,intrb,intc, node *p) __attribute__((optimize("-O2"))){
- if(lb >= p->rb || rb <= p->lb)return;
- if(lb <= p->lb && rb >= p->rb) { p->dec(c);return; }
- p->pushdown();
- del(lb, rb, c, p->l);
- del(lb, rb, c, p->r);
- p->pushup();
- }
- inline voidcover(intlb,intrb) __attribute__((optimize("-O2"))){
- cover(lb, rb, root);
- }
- inline voidcover(intlb,intrb, node *p) __attribute__((optimize("-O2"))){
- if(lb >= p->rb || rb <= p->lb)return;
- if(lb <= p->lb && rb >= p->rb) { p->cover(0);return; }
- p->pushdown();
- cover(lb, rb, p->l);
- cover(lb, rb, p->r);
- p->pushup();
- }
- inline res query(intlb,intrb) __attribute__((optimize("-O2"))){
- return query(lb, rb, root);
- }
- inline res query(intlb,intrb, node *p) __attribute__((optimize("-O2"))){
- if(lb >= p->rb || rb <= p->lb)return res(INF, INF);
- if(lb <= p->lb && rb >= p->rb)returnp->ans;
- p->pushdown();
- returnadd(query(lb, rb, p->l), query(lb, rb, p->r));
- }
- inline voidrecover() __attribute__((optimize("-O2"))){
- root->recover();
- }
- } st;
- struct edge {
- int u, v, l;
- edge *nxt;
- edge() {}
- edge(int_u,int_v,int_l, edge *_nxt) : u(_u), v(_v), l(_l), nxt(_nxt) {}
- } mp[MAXINT *2], *head[MAXINT];
- inline voidaddedge(intu,intv,int l) {
- mp[cnt] = edge(u, v, l, head[u]);
- head[u] = &mp[cnt++];
- mp[cnt] = edge(v, u, l, head[v]);
- head[v] = &mp[cnt++];
- }
- inline voiddfs1(int p) {
- sz[p] =1;
- iter(i, p) {
- if(i->v == fa[p])continue;
- fa[i->v] = p; dep[i->v] = dep[p] +1; va[i->v] = i->l;
- dfs1(i->v);
- sz[p] += sz[i->v];
- }
- }
- inline voiddfs2(int p) {
- intmx =0, gs =0;
- dfn[p] = cnt_dfn++;
- iter(i, p) {
- if(i->v == fa[p])continue;
- if(sz[i->v] > mx) {
- mx = sz[i->v];
- gs = i->v;
- }
- }
- if(gs ==0)return;
- top[gs] = top[p];
- dfs2(gs);
- iter(i, p) {
- if(i->v == fa[p] || i->v == gs)continue;
- top[i->v] = i->v;
- dfs2(i->v);
- }
- dfne[p] = cnt_dfn;
- }
- inline voidmodify(intl,intr,int c) {
- while(top[l] != top[r]) {
- if(dep[top[l]] > dep[top[r]]) {
- st.del(dfn[top[l]], dfn[l] +1, c, st.root);
- l = fa[top[l]];
- }
- else {
- st.del(dfn[top[r]], dfn[r] +1, c, st.root);
- r = fa[top[r]];
- }
- }
- st.del(min(dfn[r], dfn[l]), max(dfn[r], dfn[l]) +1, c, st.root);
- }
- inline voidcover(int p) {
- st.cover(dfn[p], dfne[p]);
- }
- inline res query(intl,int r) {
- res ans(INF, INF);
- while(top[l] != top[r]) {
- if(dep[top[l]] > dep[top[r]]) {
- ans = add(st.query(dfn[top[l]], dfn[l] +1), ans);
- l = fa[top[l]];
- }
- else {
- ans = add(st.query(dfn[top[r]], dfn[r] +1), ans);
- r = fa[top[r]];
- }
- }
- ans = add(st.query(min(dfn[r], dfn[l]), max(dfn[r], dfn[l]) +1), ans);
- return ans;
- }
- inline voidget_input() __attribute__((optimize("-O2")));
- inline voidwork() __attribute__((optimize("-O2")));
- int main() {
- get_input();
- work();
- return 0;
- }
- inline void work() {
- dfs1(1);
- dfs2(1);
- rep1(i, n) val[dfn[i]] = va[i];
- rep1(i, n) toid[dfn[i]] = i;
- val[1] = INF;
- st.maketree(1, n +1, st.root);
- while(m--) {
- st.recover();
- intk = read();
- ll ans =0;
- while(k--) {
- intp = read();
- res ret = query(1, p);
- ans += ret.v;
- cover(toid[ret.p]);
- modify(1, fa[toid[ret.p]], ret.v);
- }
- printf("%lld\n", ans);
- }
- }
- inline void get_input() {
- BUF[fread(BUF, 1,30000000, stdin)] ='\0';
- buf = BUF;
- n = read();
- rep0(i, n -1) {
- intu = read(), v = read(), l = read();
- addedge(u, v, l);
- }
- m = read();
- }
- /*
- 10
- 1 5 13
- 1 9 6
- 2 1 19
- 2 4 8
- 2 3 91
- 5 6 8
- 7 5 4
- 7 8 31
- 10 7 9
- 1
- 4 5 7 8 3
- */
来源: http://www.bubuko.com/infodetail-2093390.html