前言
水题？屑题！
题目
讲解
对于中位数，我们没有什么好的解决方法，只好先按边权从小到大排序。
考虑边 (i) 的权值如果可以作为中位数会有什么特性？或者说这棵生成树有什么特性？
显然在它前面的边在这棵树中占了 (n/2-1) 条边，后面的边也同样如此。
所以我们根据前缀和后缀贪心选边加入，类似于 ( t Kruskal) 算法，对于每条边我们检查一下是否满足条件即可。
这是你可能会问了，难道这样一定可以保证这条边的权值可以作为中位数吗？
是的！我们可以构造出一组这样的解，证明如下：
我们令前缀贪心选出来的边的集合为 (U),后缀为 (V)。
考虑如果 (U,V) 的大小都是 (n/2-1) ，而这个图又是连通的，那么这条边一定可以加到生成树中。
否则，我们任意选一个大小大于 (n/2-1) 的集合，把它所有的边全部加入生成树，然后我们加入当前判断的这条边，如果形成环，那么断掉环上的一条边即可。
然后我们把另一个集合的边也依次加进去，类似的，如果成环，那么删掉一条环上之前那个集合的边，由于图是连通的，我们一定可以构造出这样一个解。
超级大坑点：如果一条边 (x) 的权值根据我们的算法跑出来它不能作为中位数，但是某条边 (y) 可以，而且和 (x) 边的权值相同，那么 (x) 也是合法的，其权值可以作为中位数！
代码
//12252024832524
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int MAXM = 200005;
int n,m;
int pre[MAXM],suf[MAXM];
bool ans[MAXM];
map<int,bool> check;
LL Read()
{
LL x = 0,f = 1;char c = getchar();
while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();}
while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();}
return x * f;
}
TT void Put1(T x)
{
if(x > 9) Put1(x/10);
putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
if(x < 0) putchar('-'),x = -x;
Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}
struct edge
{
int u,v,val,ID;
void Get(int x)
{
u = Read();
v = Read();
val = Read();
ID = x;
}
bool operator < (const edge&px)const{
return val < px.val;
}
}e[MAXM];
int f[MAXN];
void clr(){for(int i = 1;i <= n;++ i) f[i] = i;}
int findSet(int x)
{
if(f[x] != x) f[x] = findSet(f[x]);
return f[x];
}
int unionSet(int x,int y)
{
int u = findSet(x),v = findSet(y);
if(u == v) return 0;
f[u] = v; return 1;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
for(int T = Read(); T ;-- T)
{
check.clear();
n = Read(); m = Read();
for(int i = 1;i <= m;++ i) e[i].Get(i),ans[i] = 0;
sort(e+1,e+m+1);
clr();
for(int i = 1;i <= m;++ i) pre[i] = pre[i-1] + unionSet(e[i].u,e[i].v);
clr();
suf[m+1] = 0;
for(int i = m;i >= 1;-- i) suf[i] = suf[i+1] + unionSet(e[i].u,e[i].v);
for(int i = 1;i <= m;++ i)
if(pre[i-1] >= n/2-1 && suf[i+1] >= n/2-1)
ans[e[i].ID] = 1,check[e[i].val] = 1;
for(int i = 1;i <= m;++ i) if(!ans[e[i].ID] && check[e[i].val]) ans[e[i].ID] = 1;
for(int i = 1;i <= m;++ i)
if(ans[i]) putchar('1');
else putchar('0');
putchar('
');
}
return 0;
}