85pts 球条
查看原帖
85pts 球条
759710
LuoFeng_Nanami楼主2025/8/5 12:09

rt,WA #1#2#4,都是树形小数据,不知为何一直挂。。。

//Fuyutsuki Saki Fan Club
//2025/08/05 10:29
//LuoFeng_Nanami ver. 
#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i, a, b) for(rll i = a; i <= b; i++)
#define Fdn(i, a, b) for(rll i = a; i >= b; i--)
#define pii pair<int, int>
#define int ll
#define fi first
#define se second
#define ld long double
#define pid pair<int, ld>
#define ull unsigned ll
#define lb(x) lowbit(x)
#define lwb lower_bound
#define upb upper_bound

using namespace std;
mt19937_64 rnd(time(0));

const int inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;
const ld eps = 1e-9;
const int maxn = 3e5 + 7, maxlg = 20;

int n, m, q;
struct edge { int v, w, id; } ;
vector<edge> G[maxn];
vector<pii> T[maxn];
int dfn[maxn], dfc, low[maxn], stk[maxn], top, bel[maxn], cnt, val[maxn], fval[maxn], vis[maxn], sum[maxn];

inline void Pop(int u) {
	cnt++;
	for(int x = 0; x != u && top; ) bel[x = stk[top--]] = cnt;
}

inline void Tarjan(int u, int i) {
	dfn[u] = low[u] = ++dfc, stk[++top] = u;
	for(auto [v, w, id] : G[u]) {
		if(i == id) continue ;
		if(!dfn[v]) {
			Tarjan(v, id);
			low[u] = min(low[u], low[v]);
			if(low[v] > dfn[u]) Pop(v);
		} else low[u] = min(low[u], dfn[v]);
	}
}

int mi[maxlg][maxn], dep[maxn];

inline int Get(int u, int v) { return (dep[u] < dep[v] ? u : v); }

inline void dfs(int u, int fa) {
	mi[0][dfn[u] = ++dfc] = fa, dep[u] = dep[fa] + 1, sum[u] = sum[fa] + val[u] + fval[u];
	for(auto [v, w] : T[u]) {
		if(v == fa) continue ;
		fval[v] = w;
		dfs(v, u);
	}
}

inline void Init() {
	int Lim = log2(cnt);
	F(i, 1, Lim) F(j, 1, cnt - (1 << Lim) + 1) mi[i][j] = Get(mi[i - 1][j], mi[i - 1][j + (1 << (i - 1))]);
}

inline int LCA(int u, int v) {
	if(u == v) return u;
	u = dfn[u], v = dfn[v];
	if(u > v) swap(u, v);
	int s = log2(v - u++);
	return Get(mi[s][u], mi[s][v - (1 << s) + 1]);
}

inline int GVal(int u, int v) {
	int d = LCA(u, v);
	return sum[u] + sum[v] - 2 * sum[d] + val[d];
}



signed main() {
//	freopen("saki.in", "r", stdin);
//	freopen("saki.out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	F(i, 1, m) {
		int u, v, w; cin >> u >> v >> w;
		G[u].push_back({v, w, i}), G[v].push_back({u, w, i});
	} Tarjan(1, 0); Pop(1);
	F(u, 1, n) for(auto [v, w, i] : G[u]) {
		if(vis[i]) continue ; vis[i] = 1;
		if(bel[u] == bel[v]) val[bel[u]] += w;
		else T[bel[u]].push_back({bel[v], w}), T[bel[v]].push_back({bel[u], w}); 
	}
    memset(dfn, 0, sizeof dfn);
	dfc = 0;
	dfs(1, 0);
	Init();
	cin >> q;
	F(i, 1, q) {
		int u, v; cin >> u >> v;
		cout << (GVal(bel[u], bel[v]) ? "YES\n" : "NO\n");
	}
	

    return 0;
}
2025/8/5 12:09
加载中...