#7 TLE 萌新求助
  • 板块学术版
  • 楼主Diang
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/1/19 12:58
  • 上次更新2023/10/28 11:58:15
查看原帖
#7 TLE 萌新求助
368934
Diang楼主2022/1/19 12:58
#include<bits/stdc++.h>
#define rep(x) for(int i = head[x], y = to[i] ; i ; i = nex[i], y = to[i])
using namespace std;
typedef long long int xt;
const int sn = 2.5e5 + 500;
const int se = sn * 2;
inline void in(int &x){
	int nt;
	while(!isdigit(nt = getchar())); x = nt ^ '0';
	while(isdigit(nt = getchar())) x = (x << 1) + (x << 3) + (nt ^ '0');
}
void prt(const xt &x) {
	if(x > 9) prt((x / 10ll));
	putchar((x%10ll) ^ '0');
}
int n, m, k;

int head[sn], nex[se], lth[se], to[se], amtE;
void addE(int x, int y, int z) { to[++amtE] = y; lth[amtE] = z; nex[amtE] = head[x]; head[x] = amtE; }
void aue(int x, int y, int z) { addE(x, y, z); addE(y, x, z); }

int amtF;
int fhead[sn];
void addF(int x, int y) { to[++amtF] = y; nex[amtF] = fhead[x]; fhead[x] = amtF; }
void aueF(int x, int y) { addF(x, y); addF(y, x); }
#define Erep(x) \
for(int i = fhead[x], y = to[i] ; i ; i = nex[i], y = to[i])

int siz[sn], dep[sn], son[sn], fa[sn];
void dfs1(int x, int f) {
    fa[x] = f; siz[x] = 1; dep[x] = dep[f] + 1;
    rep(x) if(y != f) {
        dfs1(y, x);
        siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) y = son[x];
    }
}
int top[sn], dfn[sn], ti;
xt val[sn];
void dfs2(int x, xt V) {
    dfn[x] = ++ti;
	val[x] = V;
	top[x] = (x == son[fa[x]] ? top[fa[x]] : x);
    rep(x)
		if(y != fa[x])
			dfs2(y, min(V, (xt)lth[i]));
}
int lca(int x, int y) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

int key[sn];
xt dfs3(int x, int fa) {
    xt sum = 0;
    Erep(x) if(y != fa) { sum += dfs3(y, x); }
    fhead[x] = 0;
    if(key[x]) { key[x] = 0; return val[x]; }
    else return min(val[x], sum);
}

int stk[sn], Stop;
int kp[sn];
bool cmp(int x, int y) { return dfn[x] < dfn[y]; }
void build(int *kp)
{
    amtF = 0; Stop = 0;
    sort(kp + 1, kp + k + 1, cmp);
    stk[++Stop] = 1;
    for(int i = 1 ; i <= k ; ++i) {
    	key[kp[i]] = 1;
        int l = lca(kp[i], stk[Stop]);
        while(stk[Stop] != l) {
            int cur = stk[Stop]; --Stop;
            if(dfn[stk[Stop]] < dfn[l]) stk[++Stop] = l;
            aueF(stk[Stop], cur);
        }
        stk[++Stop] = kp[i];
    }
    for(int i = 1 ; i <= Stop - 1 ; ++i) aueF(stk[i], stk[i + 1]);
}

int main()
{
    int x, y, z;
    in(n);
    for(int i = 1 ; i <= n - 1 ; ++i)
		in(x), in(y), in(z), aue(x, y, z);
    amtF = amtE;
    dfs1(1, 0);
    dfs2(1, 1ll << 60ll);

	in(m);
    for(int i = 1 ; i <= m ; ++i)
    {
    	in(k);
        for(int j = 1 ; j <= k ; ++j) in(kp[j]);
        build(kp);
        prt(dfs3(1, 0)); putchar('\n');
    }

    return 0;
}
2022/1/19 12:58
加载中...