CF1656E Equal Tree Sums Sol()-其他

CF1656E Equal Tree Sums Sol()

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = N << 4;
int t, n, cnt, qu[N], dep[N], lst[N], res[N], head[N];
struct Edge { int to, nxt; } e[N << 1];

namespace fast_io {
int it, ed, ot, t; char stk[20], bf[N + 50], ob[N + 50];
#define gc (it == ed && (ed = (it = 0) + fread(bf, 1, N, stdin), it == ed))? EOF : bf[it++]
template <typename T> inline void read(T &x) {
x = 0; char ch = gc; int f = 1;
for (; !isdigit(ch); ch = gc) if (ch == '-') f = -1;
for (; isdigit(ch); ch = gc) x = x * 10 + (ch ^ 48); x *= f; return ;
} template <typename T, typename ...Args>
inline void fls() { fwrite(ob, 1, ot, stdout), ot = 0; }
template <typename T> inline void write(T x, char opt) {
if (x < 0) ob[ot++] = '-', x = -x;
while (x > 9) stk[++t] = 48 ^ (x % 10), x /= 10;
for (ob[ot++] = 48 ^ x; t; ob[ot++] = stk[t--]);
ob[ot++] = opt; if (ot > N) fls(); return ;
}

inline void addEdge(int u, int v) {
e[++cnt].to = v, e[cnt].nxt = head[u];
}

inline void solve() {
read(n); cnt = 0; for (int i = 1; i <= n; ++i) head[i] = res[i] = 0;
for (int i = 1, u, v; i < n; ++i)
int l = 1, r = 1; qu[l] = dep[l] = lst[l] = 1;
while (l <= r) {
int f = lst[l], cur = qu[l], dp = dep[l]; ++l;
for (int i = head[cur]; i; i = e[i].nxt) {
int to = e[i].to;
if (to ^ f) ++r, lst[r] = cur, qu[r] = to, dep[r] = -dp;
}
res[cur] *= dp;
}
for (int i = 1; i <= n; ++i) write(res[i], i == n? '\n' : ' ');
}

int main() {
read(t); while (t--) solve(); fast_io::fls(); return 0;
}

————————

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = N << 4;
int t, n, cnt, qu[N], dep[N], lst[N], res[N], head[N];
struct Edge { int to, nxt; } e[N << 1];

namespace fast_io {
int it, ed, ot, t; char stk[20], bf[N + 50], ob[N + 50];
#define gc (it == ed && (ed = (it = 0) + fread(bf, 1, N, stdin), it == ed))? EOF : bf[it++]
template <typename T> inline void read(T &x) {
x = 0; char ch = gc; int f = 1;
for (; !isdigit(ch); ch = gc) if (ch == '-') f = -1;
for (; isdigit(ch); ch = gc) x = x * 10 + (ch ^ 48); x *= f; return ;
} template <typename T, typename ...Args>
inline void fls() { fwrite(ob, 1, ot, stdout), ot = 0; }
template <typename T> inline void write(T x, char opt) {
if (x < 0) ob[ot++] = '-', x = -x;
while (x > 9) stk[++t] = 48 ^ (x % 10), x /= 10;
for (ob[ot++] = 48 ^ x; t; ob[ot++] = stk[t--]);
ob[ot++] = opt; if (ot > N) fls(); return ;
}

inline void addEdge(int u, int v) {
e[++cnt].to = v, e[cnt].nxt = head[u];
}

inline void solve() {
read(n); cnt = 0; for (int i = 1; i <= n; ++i) head[i] = res[i] = 0;
for (int i = 1, u, v; i < n; ++i)
int l = 1, r = 1; qu[l] = dep[l] = lst[l] = 1;
while (l <= r) {
int f = lst[l], cur = qu[l], dp = dep[l]; ++l;
for (int i = head[cur]; i; i = e[i].nxt) {
int to = e[i].to;
if (to ^ f) ++r, lst[r] = cur, qu[r] = to, dep[r] = -dp;
}
res[cur] *= dp;
}
for (int i = 1; i <= n; ++i) write(res[i], i == n? '\n' : ' ');
}

int main() {
read(t); while (t--) solve(); fast_io::fls(); return 0;
}