Problem:


Score : 1000 points

Problem Statement

You are given a tree with N vertices. The vertices are numbered 0 through N-1, and the edges are numbered 1 through N-1.
Edge i connects Vertex x_i and y_i, and has a value a_i.
You can perform the following operation any number of times:

Choose a simple path and a non-negative integer x, then for each edge e that belongs to the path, change a_e by executing a_e ← a_e ⊕ x (⊕ denotes XOR).

Your objective is to have a_e = 0 for all edges e.
Find the minimum number of operations required to achieve it.

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ N-1

0 ≤ a_i ≤ 15

The given graph is a tree.

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1 a_1
x_2 y_2 a_2
:
x_{N-1} y_{N-1} a_{N-1}

Output

Find the minimum number of operations required to achieve the objective.

Sample Input 1

5
0 1 1
0 2 3
0 3 6
3 4 4

Sample Output 1

3

The objective can be achieved in three operations, as follows:

First, choose the path connecting Vertex 1, 2, and x = 1.

Then, choose the path connecting Vertex 2, 3, and x = 2.

Lastly, choose the path connecting Vertex 0, 4, and x = 4.

Sample Input 2

2
1 0 0

Sample Output 2

0



Sample input:
5
0 1 1
0 2 3
0 3 6
3 4 4


Sample output:
3

Submission status: Wrong Answer

Solution code:
from collections import Counter
from functools import reduce
from itertools import combinations
from operator import xor

n = int(input())
nodes = [0] * n
for _ in range(n - 1):
    x, y, a = map(int, input().split())
    nodes[x] ^= a
    nodes[y] ^= a

c = Counter(nodes)
del c[0]
ans = 0
remains = set()
for i, v in c.items():
    ans += v // 2
    if v % 2:
        remains.add(i)

for r in (3, 4, 5):
    while len(remains) < r * 2:
        for ns in combinations(remains, r):
            if reduce(xor, ns) == 0:
                remains.difference_update(ns)
                ans += r - 1
                break
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
from itertools import combinations
from operator import xor

n = int(input())
nodes = [0] * n
for _ in range(n - 1):
    x, y, a = map(int, input().split())
    nodes[x] ^= a
    nodes[y] ^= a

c = Counter(nodes)
del c[0]
ans = 0
remains = set()
for i, v in c.items():
    ans += v // 2
    if v % 2:
        remains.add(i)

for r in (3, 4, 5):
    while not r < len(remains) < r * 2:
        for ns in combinations(remains, r):
            if reduce(xor, ns) == 0:
                remains.difference_update(ns)
                ans += r - 1
                break
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
from itertools import combinations
from operator import xor

n = int(input())
nodes = [0] * n
for _ in range(n - 1):
    x, y, a = map(int, input().split())
    nodes[x] ^= a
    nodes[y] ^= a

c = Counter(nodes)
ans = 0
remains = set()
for i, v in c.items():
    if i == 0:
        continue
    ans += v // 2
    if v % 2:
        remains.add(i)

for r in (3, 4, 5):
    while True:
        for ns in combinations(remains, r):
            if reduce(xor, ns) == 0:
                remains.difference_update(ns)
                ans += r - 1
                break
        else:
            break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
B = [0]*N
for i in range(N-1):
    x, y, a = map(int, input().split())
    B[x] ^= a
    B[y] ^= a
D = {}
for b in B:
    D[b] = D.get(b, 0) + 1
D[0] = 0
ans = 0
first = 0
for b in D:
    ans += D[b]//2
    if D[b]%2:
        first |= 1 << b

A = [0]*(1 << 16)
for i in range(1, 1<<16):
    bit = i & -i
    l = len(bin(bit))-3
    A[i] = A[i ^ bit] ^ l

memo = {0: 0}
def dfs(state):
    if state in memo:
        return memo[state]
    cur = state
    res = 10**9+7
    while cur:
        if A[cur] == 0:
            res = min(res, dfs(state ^ cur) + bin(cur).count('1')-1)
        cur -= 1
        cur &= state
    memo[state] = res
    return res
ans += dfs(first)
print(ans)

Submission status: Runtime Error

Solution code:
#pragma region revive
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inl inline
#define re register int
#define fa(x) t[x].fa
#define son(x, y) t[x].child[y]
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define ll long long
#define ull unsigned long long
const int inf = 0x3f3f3f3f;
#define lowbit(x) ((x) & (-x))
using namespace std;
//#ifndef _DEBUG
//#define getchar() (*(IOB.in.p++))
//#define putchar(c) (*(IOB.out.p++) = (c))
//#define io_eof() (IOB.in.p >= IOB.in.pend)
//struct IOBUF {
//	struct {
//		char buff[1 << 27], *p, *pend;
//	} in;
//	struct {
//		char buff[1 << 27], *p;
//	} out;
//	IOBUF() {
//		in.p = in.buff;
//		out.p = out.buff;
//		in.pend = in.buff + fread(in.buff, 1, 1 << 27, stdin);
//	}
//	~IOBUF() { fwrite(out.buff, 1, out.p - out.buff, stdout); }
//} IOB;
//#endif
template <typename IO>
inl void write(IO x) {
	if (x == 0) return (void)putchar('0');
	if (x < 0) putchar('-'), x = -x;
	static char buf[30];
	char *p = buf;
	while (x) {
		*(p++) = x % 10 + '0';
		x /= 10;
	}
	while (p > buf)
		putchar(*(--p));
}
inl void writestr(const char *s) {
	while (*s != 0)
		putchar(*(s++));
}
template <typename IO>
inl void writeln(IO x) { write(x), putchar('\n'); }
template <typename IO>
inl void writesp(IO x) { write(x), putchar(' '); }
inl int readstr(char *s) {
	char *begin = s, c = getchar();
	while (c < 33 || c > 127) {
		c = getchar();
	}
	while (c >= 33 && c <= 127) {
		*(s++) = c;
		c = getchar();
	}
	*s = 0;
	return s - begin;
}
template <typename IO>
inl IO read() {
	IO x = 0;
	register bool w = 0;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') w = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return w ? -x : x;
}
template <>
inl double read<double>() {
	double x = 0;
	int w = 0, y = 0;
	ll z = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') w = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9' || c == '.') {
		if (c == '.') {
			y = 1, c = getchar();
			continue;
		}
		x = x * 10 + (c ^ 48);
		if (y) z *= 10;
		c = getchar();
	}
	return (w ? -x : x) / z;
}
#pragma endregion
int n, b[1 << 16], f[1 << 16], s;
int a[100001], o[16], ans;
inl int dp(int i) {
	if (f[i] < inf) return f[i];
	for (re x = 1; x <= 15; x++) {
		if (((1 << x) & i) == 0) continue;
		for (re y = 1; y <= 15; y++) {
			if (x == y) continue;
			if (((1 << y) & i) == 0) continue;
			re z = x ^ y, p = (((i ^ (1 << z)) ^ (1 << x)) ^ (1 << y));
			if ((1 << z) & i)
				f[i] = min(f[i], dp(p) + 2);
			else
				f[i] = min(f[i], dp(p) + 1);
		}
	}
	return f[i];
}
int main() {
	n = read<int>();
	for (re x, y, z, i = 1; i < n; i++) {
		x = read<int>() + 1, y = read<int>() + 1, z = read<int>();
		a[x] ^= z, a[y] ^= z;
	}
	for (re i = 1; i <= n; i++) o[a[i]]++;
	for (re i = 1; i <= 15; i++) {
		if (o[i] >= 2) {
			ans += o[i] / 2;
			o[i] = o[i] & 1;
		}
		if (o[i]) s |= (1 << i);
	}
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	ans += dp(s);
	if (ans) writeln(ans);
}

Submission status: Runtime Error

Solution code:
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=200000+10;

int w[N],cnt[20],f[1<<15],sxor[1<<15];

int main() {
	int n=read();
	for (re int i=1;i<n;++i) {
		int u=read()+1,v=read()+1,val=read();
		w[u]^=val,w[v]^=val;
	}
	for (re int i=1;i<=n;++i) ++cnt[w[i]];
	int ans=0,s=0;
	for (re int i=1;i<=15;++i) ans+=cnt[i]/2,s|=(cnt[i]&1)<<(i-1);
	for (re int i=1;i<(1<<15);++i) f[i]=f[i>>1]+(i&1);
	for (re int i=1;i<(1<<15);++i) --f[i];
	for (re int i=1;i<(1<<15);++i)
		for (re int j=1;j<=15;++j)
			if (i&(1<<(j-1))) sxor[i]^=j;
	for (re int i=1;i<(1<<15);++i) {
		if (sxor[i]) continue;
		for (re int j=i&(i-1);j;j=(j-1)&i)
			if (!sxor[j]) f[i]=min(f[i],f[j]+f[i^j]);
	}
	printf("%d\n",ans+f[s]);
	return 0;
}

Submission status: Runtime Error

Solution code:
N = int(input())
B = [0]*N
for i in range(N-1):
    x, y, a = map(int, input().split())
    B[x] ^= a
    B[y] ^= a
D = {}
for b in B:
    D[b] = D.get(b, 0) + 1
D[0] = 0
ans = 0
first = 0
for b in D:
    ans += D[b]//2
    if D[b]%2:
        first |= 1 << b

A = [0]*(1 << 15)
for i in range(1, 1<<15):
    bit = i & -i
    l = len(bin(bit))-3
    A[i] = A[i ^ bit] ^ l

memo = {0: 0}
def dfs(state):
    if state in memo:
        return memo[state]
    cur = state
    res = 10**9+7
    while cur:
        if A[cur] == 0:
            res = min(res, dfs(state ^ cur) + bin(cur).count('1')-1)
        cur -= 1
        cur &= state
    memo[state] = res
    return res
ans += dfs(first)
print(ans)