TLE on #10 求条
查看原帖
TLE on #10 求条
1062683
lottle1212__楼主2025/2/4 10:42

写得有些奇怪的话见谅

#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
	res=0; bool f=false; char ch=getchar();
	while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
	res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const ll INF=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f; 
const int maxn=2.5e5, maxlg=18;
const int N=maxn+10, lgN=maxlg+2;
int n, m, H[N], _H[N], dfn[N], dep[N], fa[N][lgN], st[N][lgN], a[N<<1], h[N], edge_cnt, idx; bool sign[N]; ll dp[N];
struct Edge { int nxt, to, w; } E[N<<2];
void add(int H[], int u, int v, int w) { E[++edge_cnt]={H[u], v, w}; H[u]=edge_cnt; }
//wmr
void dfs(int u, int pre) {
	dep[u]=dep[pre]+1; dfn[u]=++idx;
	L(i, 1, maxlg) fa[u][i]=fa[fa[u][i-1]][i-1], st[u][i]=min(st[u][i-1], st[fa[u][i-1]][i-1]);
	ACN(i, H[u]) {
		int v=E[i].to;
		if (v==pre) continue;
		fa[v][0]=u, st[v][0]=E[i].w;
		dfs(v, u);
	}
}
pii lca(int u, int v) {
	int res=inf;
	if (dep[u]<dep[v]) swap(u, v);
	R(i, maxlg, 0) if (dep[fa[u][i]]>=dep[v]) res=min(res, st[u][i]), u=fa[u][i];
	if (u==v) return make_pair(u, res);
	R(i, maxlg, 0) if (fa[u][i]!=fa[v][i]) res=min(res, min(st[u][i], st[v][i])), u=fa[u][i], v=fa[v][i];
	res=min(res, min(st[u][0], st[v][0]));
	return make_pair(fa[u][0], res);
}
//incra
bool cmp(int x, int y) { return dfn[x]<=dfn[y]; }
void calc(int u, int pre) {
	if (sign[u]) return dp[u]=INF, void();
	else dp[u]=0; 
	ACN(i, _H[u]) {
		int v=E[i].to;
		if (v==pre) continue;
//		printf("%d %d %d\n", u, v, E[i].w);
		calc(v, u);
		dp[u]+=min(dp[v], (ll)E[i].w);
	}
}
//lottle
signed main() {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	rd(n);
	L(i, 1, n-1) { int u, v, w; rd(u, v, w); add(H, u, v, w); add(H, v, u, w); }
	ms(st, 0x3f);
	dfs(1, 0);
	rd(m);
	const int Edge_cnt=edge_cnt;
	while (m--) {
		int kn; rd(kn);
		L(i, 1, kn) rd(a[i]), h[i]=a[i], sign[a[i]]=true;
		sort(a+1, a+kn+1, cmp);
		int _kn=kn;
		L(i, 1, kn-1) a[++_kn]=lca(a[i], a[i+1]).fst;
		a[++_kn]=1;
		sort(a+1, a+_kn+1, cmp); _kn=unique(a+1, a+_kn+1)-a-1;
		L(i, 1, _kn) _H[a[i]]=0; edge_cnt=Edge_cnt;
		L(i, 1, _kn-1) { int j=lca(a[i], a[i+1]).fst, w=lca(j, a[i+1]).scd; add(_H, j, a[i+1], w); add(_H, a[i+1], j, w); }
		calc(1, 0);
		printf("%lld\n", dp[1]);
		L(i, 1, kn) sign[h[i]]=false;
	}
	return 0;
}
2025/2/4 10:42
加载中...