水一发题解。目前有的那一篇题解感觉写的完全没有道理。

考虑二分答案 $w$，则边权 $\ge w$ 的边一定是没用的。对于剩下来的图，一个必要条件是：每个连通块的大小 $\ge 2$。

实际上，这个条件也是充分的。我们可以先删一些边使得每一个连通块都是二分图，然后二分图染色即可。这样构造的正确性显然。

根据上述分析，可以很容易的写出 check 和构造。复杂度 $\mathcal{O}((n+m)\log V)$，可能可以通过。

注意到我们只需要在 $m$ 个边权里二分即可，复杂度 $\mathcal{O}((n+m)\log m)$，可以通过。

可能轻微卡常，这一点差评。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define F(i, a, b) for (int i = (a); i <= (b); i ++ )
#define DF(i, a, b) for (int i = (a); i >= (b); i -- )
inline void chkmin(int& a, int b) { if (a > b) a = b; }
inline void chkmax(int& a, int b) { if (a < b) a = b; }

const int N = 500010, M = 2 * N, INF = 5e14;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
int col[N];
bool st[N];

void add(int a, int b, int c)
{
	e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int comp(int u, int lim)
{
	queue<int> q;
	int res = 0;
	q.push(u); st[u] = true;
	while (q.size())
	{
		int t = q.front(); q.pop();
		res ++ ;
		for (int i = h[t]; ~i; i = ne[i])
		{
			int j = e[i];
			if (w[i] > lim || st[j]) continue;
			st[j] = true;
			q.push(j);
		}
	}
	return res;
}

bool check(int mid)
{
	F(i, 1, n) st[i] = 0;
	F(i, 1, n) if (st[i]) continue; else if (comp(i, mid) == 1) return false;
	return true;
}

void dfs(int u, int lim)
{
	st[u] = true;
	for (int i = h[u]; ~i; i = ne[i])
	{
		int j = e[i];
		if (w[i] > lim || st[j]) continue;
		col[j] = 3 - col[u];
		dfs(j, lim);
	}
}

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(h, -1, sizeof h);
	cin >> n >> m;
	vector<int> er;
	F(i, 0, m - 1)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c), add(b, a, c);
		er.push_back(c);
	}
	sort(er.begin(), er.end());
	int l = 0, r = (int)er.size() - 1, res = INF;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (check(er[mid])) r = mid - 1, res = er[mid];
		else l = mid + 1;
	}
	cout << res << "\n";
	F(i, 1, n) st[i] = 0;
	F(i, 1, n) if (!st[i]) col[i] = 1, dfs(i, res);
	F(i, 1, n) cout << (col[i] == 1 ? 'D' : 'B');
	cout << "\n";
	return 0;
}