1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <bits/stdc++.h>
using namespace std;
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
if(ioh == iot) {
iot = (ioh = buf) + fread(buf, 1, iol, stdin);
if(ioh == iot) return -1;
}
return *ioh++;
}
template<class T>
inline void read(T& x) {
iosig = false;
for(ioc = read(); !isdigit(ioc); ioc = read()) {
if(ioc == '-') iosig = true;
}
x = 0;
while(ioc == '0') ioc = read();
for(; isdigit(ioc); ioc = read())
x = (x << 1) + (x << 3) + (ioc ^ '0');
ioh--;
if(iosig) x = -x;
}
const int maxn = 100010;
int n;
struct Node {
int u, v, w;
Node() {}
Node(int _v, int _w): u(-1), v(_v), w(_w) {}
Node(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
inline bool operator < (const Node&_n) const {
return w > _n.w;
}
};
typedef priority_queue<Node> heap;
vector<Node> edge[maxn], mst[maxn];
bool vis[maxn];
unsigned int twobuf[maxn * 100];
inline void addEdge(int u, int v, int w, vector<Node>*vc) {
vc[u].push_back(Node(u, v, w));
vc[v].push_back(Node(v, u, w));
}
inline void prim(int s = 1) {
heap q;
Node t;
q.push(Node(s, 0));
while (!q.empty()) {
t = q.top(); q.pop();
if (vis[t.v]) continue;
if (t.u != -1) addEdge(t.u, t.v, t.w, mst);
vis[t.v] = true;
for (register int i = 0; i < edge[t.v].size(); i++)
if (!vis[edge[t.v][i].v])
q.push(Node(edge[t.v][i].u, edge[t.v][i].v, edge[t.v][i].w));
}
}
int m;
int size[maxn];
inline void dfs(int u = 1, int pre = 1) {
size[u] = 1;
for (int i = 0; i < mst[u].size(); i++) {
Node *x = &mst[u][i];
if (x->v == pre) continue;
dfs(x->v, u);
size[u] += size[x->v];
twobuf[x->w + 1] = (unsigned int)size[x->v] * (n - size[x->v]);
}
}
int main() {
read(n), read(m);
for (register int i = 0, u, v, w; i < m; i++)
read(u), read(v), read(w), addEdge(u, v, w, edge);
prim();
dfs();
for(int i = 1; i <= m; i++)
twobuf[i + 1] += twobuf[i] >> 1, twobuf[i] %= 2;
unsigned int x = twobuf[m+1];
register int top = m + 1;
while(x) top++, twobuf[top] = x >> 1, twobuf[top - 1] = x % 2, x = twobuf[top];
while(!twobuf[top]) top--;
reverse(twobuf + 1, twobuf + top + 1);
for (int i = 1; i <= top; i++)
cout << twobuf[i];
return 0;
}
|
