求助,悬关,帮助我的人明年稳 Au
查看原帖
求助,悬关,帮助我的人明年稳 Au
620253
MvemiY楼主2024/7/21 09:46
#include<bits/stdc++.h>
#define E(v, w) (Edge){v, w}
#define int long long 
using namespace std;
const int MAXN = 1e5 + 10;
inline int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
} 

int n, q, k, f[MAXN], pre[MAXN], a[MAXN], tot, st1[MAXN][20], b[MAXN], st2[MAXN][20];
int fa[MAXN], Bigson[MAXN], dep[MAXN], top[MAXN], siz[MAXN], dfn[MAXN], id[MAXN];
struct Edge{
	int v, w;
};
vector <Edge> tr[MAXN];
struct Node{
	int u, val, idd;
	bool operator < (Node x) const {return this->idd < x.idd;}
	bool operator > (Node x) const {return this->idd > x.idd;}
	bool operator == (Node x) const {return this->idd == x.idd;}
}p[MAXN];

void dfs1(int u, int Fa){
	dep[u] = dep[Fa] + 1;
	fa[u] = Fa;
	siz[u] = 1;
	int len = tr[u].size();
	for(int i = 0; i < len; i++){
		int v = tr[u][i].v, w = tr[u][i].w;
		if(v == Fa) continue;
		pre[v] = pre[u] + w;
		a[v] = w;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[Bigson[u]])
			Bigson[u] = v;
	}
}

void dfs2(int u, int head){
	dfn[++tot] = u;
	id[u] = tot;
//	cout << u << ' ' << id[u] << endl;
	top[u] = head;
	if(Bigson[u])
		dfs2(Bigson[u], head);
	int len = tr[u].size();
	for(int i = 0; i < len; i++){
		int v = tr[u][i].v;
		if(v == Bigson[u] || v == fa[u]) continue;
		dfs2(v, v);
	}
}

bool cmp(Node x, Node y){
	return x.idd < y.idd;
}

void init1(){
	for(int i = 1; i <= k; i++)
		st1[i][0] = p[i].val;
	for(int j = 1; j <= 20; j++){
		for(int l = 1, r = l + (1<<j) - 1; r <= n; l++, r++)
			st1[l][j] = min(st1[l][j-1], st1[r-(1<<(j-1))+1][j-1]);
	}
}

int query1(int l, int r){
	int lg = log2(r-l+1);
	return min(st1[l][lg], st1[r-(1<<lg)+1][lg]);
}

int work(int u){
	int l = id[u], r = id[u] + siz[u] - 1;
	int L = lower_bound(p+1, p+1+k, (Node){-1, -1, l}) - p;
	int R = upper_bound(p+1, p+1+k, (Node){-1, -1, r}) - p - 1;
	if(L > R) return INT_MAX;
	return query1(L, R);
}

void dfs3(int u){
	f[u] = work(u) - pre[u];
	int len = tr[u].size();
	for(int i = 0; i < len; i++){
		int v = tr[u][i].v, w = tr[u][i].w;
		if(v == fa[u]) continue;
		dfs3(v);
		f[v] = min(f[v], f[u] + w);
	}
} 

void init2(){
	for(int i = 1; i <= n; i++)
		st2[i][0] = f[dfn[i]];
	for(int j = 1; j <= 20; j++){
		for(int l = 1, r = l + (1<<j) - 1; r <= n; l++, r++)
			st2[l][j] = min(st2[l][j-1], st2[r-(1<<(j-1))+1][j-1]);
	}
}

int query2(int l, int r){
	int lg = log2(r-l+1);
	return min(st2[l][lg], st2[r-(1<<lg)+1][lg]);
}

pair <int,int> query_path(int u, int v){
	int res = INT_MAX;
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])
			swap(u, v);
		res = min(res, query2(id[top[u]], id[u] ));
		u = fa[top[u]];
	}
	if(dep[u] < dep[v]) swap(u, v);
	res = min(res, query2(id[v], id[u]));
	return {v, res};
}

signed main(){
	n = read(), q = read(), k = read();
	for(int i = 1; i < n; i++){
		int u = read(), v = read(), w = read();
		tr[u].push_back(E(v, w));
		tr[v].push_back(E(u, w));
	}
	dfs1(1, 0);
	dfs2(1, 1);
	for(int i = 1; i <= k; i++)
		p[i].u = read(), p[i].idd = id[p[i].u], p[i].val = pre[p[i].u];
	sort(p+1, p+1+k, cmp);
	init1();
	dfs3(1);
	init2();
	while(q--){
		int u = read(), v = read();
		pair <int,int> tmp = query_path(u, v);
		int lca = tmp.first, az = tmp.second;
//		cout << pre[u] << ' ' << pre[v] << ' ' << lca<< endl; 
		printf("%lld\n", pre[u] + pre[v] - 2*pre[lca] + 2*az);
	}
	return 0;
}

不知道为什么,只拿了 20 分,hack 数据也过了。帮帮我吧,QWQ

2024/7/21 09:46
加载中...