結果

問題 No.2377 SUM AND XOR on Tree
ユーザー Hoget157Hoget157
提出日時 2023-07-07 21:46:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,029 ms / 4,000 ms
コード長 11,313 bytes
コンパイル時間 3,644 ms
コンパイル使用メモリ 257,212 KB
実行使用メモリ 22,076 KB
最終ジャッジ日時 2023-09-28 22:50:52
合計ジャッジ時間 22,730 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1,023 ms
15,512 KB
testcase_09 AC 1,028 ms
15,404 KB
testcase_10 AC 1,011 ms
15,640 KB
testcase_11 AC 1,020 ms
15,408 KB
testcase_12 AC 1,029 ms
15,460 KB
testcase_13 AC 986 ms
15,520 KB
testcase_14 AC 991 ms
15,068 KB
testcase_15 AC 1,012 ms
15,388 KB
testcase_16 AC 991 ms
15,080 KB
testcase_17 AC 1,003 ms
15,408 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1,012 ms
15,440 KB
testcase_24 AC 995 ms
15,504 KB
testcase_25 AC 1,024 ms
15,488 KB
testcase_26 AC 393 ms
22,040 KB
testcase_27 AC 395 ms
22,028 KB
testcase_28 AC 405 ms
22,076 KB
testcase_29 AC 333 ms
15,512 KB
testcase_30 AC 339 ms
15,688 KB
testcase_31 AC 341 ms
15,612 KB
testcase_32 AC 389 ms
15,684 KB
testcase_33 AC 389 ms
15,720 KB
testcase_34 AC 385 ms
15,600 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region header
// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define isIn(x, y, h, w) ((x) >= 0 && (x) < (h) && (y) >= 0 && (y) < (w))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(auto i = (n) - 1; i >= 0; i--)
#define repi(i, n1, n2) for(auto i = (n1); i < (n2); i++)
#define rrepi(i, n1, n2) for(auto i = (n2) - 1; i >= (n1); i--)
#define rep2(i, j, n) rep(i, n) repi(j, i + 1, n)
#define DFS(...) self(self, __VA_ARGS__)
#define min_equal(v, x) lower_bound(all(v), (x)) - (v).begin()
#define min_over(v, x) upper_bound(all(v), (x)) - (v).begin()
#define max_equal(v, x) upper_bound(all(v), (x)) - (v).begin() - 1
#define max_under(v, x) lower_bound(all(v), (x)) - (v).begin() - 1

template<class T, class U> static inline vector<U> makevec(const T &n, const U &u){ return vector<U>(n, u); }
template<class T, class... Args> static inline auto makevec(const T &n, const Args&... args){ return vector<decltype(makevec(args...))>(n, makevec(args...)); }

#define in(T, ...) T __VA_ARGS__; input(__VA_ARGS__)
#define inrows(n, ...) rep(inrows_, n) inrow(__VA_ARGS__)
#define invec(T, n, ...) vector<T> __VA_ARGS__; inputvec(n, __VA_ARGS__);
#define invec2(T, n, m, x) vector<vector<T>> x(n, vector<T>(m)); input(x)
template<class T> istream &operator>>(istream &is, vector<T> &x){ for(auto &&v : x) is >> v; return is; }
template<class... T> inline void input(T&... x){ (cin >> ... >> x); }
template<class T> inline void inputvec(const T &n){ (void)n; }
template<class T, class Head, class... Tail> inline void inputvec(const T &n, Head &v, Tail&... tail){ v.resize(n); cin >> v; inputvec(n, tail...); }
inline void inrow(){}
template<class Head, class... Tail> inline void inrow(Head &x, Tail&... tail){ in(typename Head::value_type, y); x.push_back(y); inrow(tail...); }
#define INT(...) in(int, __VA_ARGS__)
#define STR(...) in(string, __VA_ARGS__)
#define CHAR(...) in(char, __VA_ARGS__)
#define VI(n, ...) invec(int, (n), __VA_ARGS__)
#define VS(n, ...) invec(string, (n), __VA_ARGS__)

#ifdef DEBUG
#define dbg(...) cout << #__VA_ARGS__ << ": "; print(__VA_ARGS__); cout << flush
#else
#define dbg(...) (static_cast<void>(0))
#endif
const string DELIMITER[] = 
#ifdef DEBUG 
	{",", "(", ")", "[", "]"};
#else
	{" ", "", "", "", ""};
#endif
ostream &operator<<(ostream &os, __int128_t x){
	if(x < 0) x *= -1, os << '-';
	vector<int> v;
	while(x) v.push_back(x % 10), x /= 10;
	if(!v.size()) return os << 0;
	for(int i = (int)v.size() - 1; i >= 0; i--) os << v[i];
	return os;
}
// template<auto T> ostream &operator<<(ostream &os, const atcoder::static_modint<T> &x){ return os << x.val(); }
// template<auto T> ostream &operator<<(ostream &os, const atcoder::dynamic_modint<T> &x){ return os << x.val(); }
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p){ return os << DELIMITER[1] << p.first << DELIMITER[0] << p.second << DELIMITER[2]; }
template<typename T, typename U = typename T::iterator, enable_if_t<!is_same_v<T, string> && !is_same_v<T, wstring>, nullptr_t> = nullptr>
ostream &operator<<(ostream &os, const T &c){
	for(auto it = c.begin(); it != c.end(); it++) os << DELIMITER[(it == c.begin()) ? 3 : 0] << *it;
	return os << DELIMITER[4];
}
template<class T> inline void prend(const T &a){ cout << a << '\n'; exit(0); }
template<class T> inline void print(const T &a){ cout << a << '\n'; }
template<class Head, class... Tail> inline void print(const Head &a, const Tail&... b){ cout << a << ' '; print(b...); }
inline void prec(const int d){ cout << fixed << setprecision(d); }

const vector<vector<string>> YN_string = {{"Yes", "No"}, {"YES", "NO"}, {"Takahashi", "Aoki"}, {"Alice", "Bob"}, {"Possible", "Impossible"}};
enum class YesNo{ Yes, YES, taka, alice, poss };

inline void i0(){}
template<class T, enable_if_t<is_integral_v<T>, nullptr_t> = nullptr, class... Tail> inline void i0(T &x, Tail&... tail){ x--; i0(tail...); }
template<class T, class... Tail> inline void i0(vector<T> &v, Tail&... tail){ for(auto &&x : v) i0(x); i0(tail...); }

template<class T> inline T div_floor(T a, T b){ if(b < 0) a = -a, b = -b; return a >= 0 ? a / b : (a + 1) / b - 1; }
template<class T> inline T div_ceil(T a, T b){ if(b < 0) a = -a, b = -b; return a <= 0 ? a / b : (a - 1) / b + 1; }
template<class T> inline T div_less(T a, T b){ return div_floor(a, b) - !(a % b); }
template<class T> inline T div_greater(T a, T b){ return div_ceil(a, b) + !(a % b); }

template<class T> inline void sort(vector<T> &v){ sort(v.begin(), v.end()); }
template<class T> inline void rsort(vector<T> &v){ sort(v.rbegin(), v.rend()); }
template<class T> inline void unique(vector<T> &v){ sort(v); v.erase(unique(v.begin(), v.end()), v.end()); }
template<class T> inline auto min(const T &a){ return *min_element(a.begin(), a.end()); }
template<class T> inline auto max(const T &a){ return *max_element(a.begin(), a.end()); }
template<class T> inline bool chmin(T &a, const T &b){ return a > b ? a = b, true : false; }
template<class T> inline bool chmax(T &a, const T &b){ return a < b ? a = b, true : false; }
template<class T> inline typename T::value_type mex(const T &st){ for(auto i = typename T::value_type(0); ; i++) if(!st.count(i)) return i; }
template<class T> inline T calc_sum(const vector<T> &v){ return accumulate(v.begin(), v.end(), T(0)); }

using ld = long double;
using ll = long long;
using l128 = __int128;
template<class T> using P = pair<T, T>;
template<class T> using tup3 = tuple<T, T, T>;
template<class T> using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T> using vec2 = vector<vector<T>>;
template<class T> using vec3 = vector<vec2<T>>;
template<class T> using uset = unordered_set<T>;
template<class T, class U> using umap = unordered_map<T, U>;

struct FastIO{ FastIO(){ cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); prec(10); } } fastio__;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
template<class T> using tree = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

#pragma endregion header

#define int long long
const int inf = 2e9;
const int INF = 2e18;
const double EPS = 1e-9;
const int MOD = 998244353;
using pi = pair<int, int>;
using ipi = pair<int, pair<int, int>>;
using pii = pair<pair<int, int>, int>;
using vi = vector<int>;
using vpi = vector<pi>;
using vs = vector<string>;
using vd = vector<double>;
using vvi = vector<vector<int>>;
// using mint = atcoder::modint1000000007;
// using mint = atcoder::modint998244353;
// using mint = atcoder::modint;
// using vm = vector<mint>;
const int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
#define YN YesNo::Yes
inline void Yes(bool end = false){ print(YN_string[(int)YN][0]); if(end) exit(0); }
inline void No(bool end = false){ print(YN_string[(int)YN][1]); if(end) exit(0); }
inline void isYes(bool x, bool end = false){ print(YN_string[(int)YN][!x]); if(end) exit(0); }

template<class T>
struct Edge{
	int from, to, id;
	T cost;
	Edge(int to, T cost) : to(to), cost(cost){}
	Edge(int from, int to, T cost) : from(from), to(to), cost(cost){}
	Edge(int from, int to, T cost, int id) : from(from), to(to), cost(cost), id(id){}
	operator int() const noexcept { return to; }
	bool operator<(const Edge &e) const{ return cost < e.cost; }
};

template<class T>
using WeightedGraph = vector<vector<Edge<T>>>;
using Graph = vector<vector<int>>;
template<class T>
using Matrix = vector<vector<T>>;

template<class T, class... Args>
void add_ud_edge(T &G, const int u, const int v, const Args&... args){
	G[u].emplace_back(v, args...);
	G[v].emplace_back(u, args...);
}

#define indg(G, n, m) Graph G(n); rep(i, m){ in(int, u, v); G[u - 1].push_back(v - 1); }
#define inudg(G, n, m) Graph G(n); rep(i, m){ in(int, u, v); add_ud_edge(G, u - 1, v - 1); }
#define inwdg(T, G, n, m) WeightedGraph<T> G(n); rep(i, m){ in(int, u, v); in(T, w); G[u - 1].emplace_back(v - 1, w); }
#define inwudg(T, G, n, m) WeightedGraph<T> G(n); rep(i, m){ in(int, u, v); in(T, w); add_ud_edge(G, u - 1, v - 1, w); }

namespace bit{
	inline bool test(const int s, const int i){ return (s >> i & 1); }
	inline void set(int &s, const int i){ s |= (1 << i); }
	inline void reset(int &s, const int i){ s &= ~(1 << i); }
	inline void flip(int &s, const int i){ s ^= (1 << i); }
	inline int orb(const int s, const int i){ return s | (1 << i); }
	inline int notb(const int s, const int i){ return s & ~(1 << i); }
	inline int xorb(const int s, const int i){ return s ^ (1 << i); }
	inline int mask(const int n){ return (1 << n) - 1; }
	inline int next_combination(const int s){
		int x = s & -s, y = s + x;
		return (((s & ~y) / x) >> 1) | y;
	}
	#define repset(s, n) rep(s, 1 << (n))
	#define repsuperset(s, t, n) for(int s = (t); s < (1 << (n)); ++s |= (t))
	#define repsubset(s, t) for(int s = (t), _ = 1; s != (t) || _; --s &= (t), _ = 0)
	#define repsubsets(s, t, n) repset(t, n) repsubset(s, t)
	#define repkset(s, n, k) for(int s = (1 << (k)) - 1; s < (1 << (n)); s = next_combination(s))
}

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }
	modint inv() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod; 
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};
using mint = modint<998244353>;

signed main(){
	INT(n);
	inudg(G, n, n - 1);
	VI(n, a);
	const int MAX = 30;
	mint ans = 0;
	rep(t, MAX){
		auto dp = makevec(n, 2, mint(0));
		auto calc = [&](auto self, int v, int par) -> void{
			dp[v][bit::test(a[v], t)] = 1;
			for(int to : G[v]){
				if(to == par) continue;
				DFS(to, v);
				mint ndp[2] = {0, 0};
				rep(i, 2){
					rep(j, 2){
						if(!i && !j) continue;
						rep(k, 2){
							ndp[(k + i * j) % 2] += dp[v][k] * dp[to][i];
						}
					}
				}
				dp[v][0] = ndp[0];
				dp[v][1] = ndp[1];
			}
		};
		calc(calc, 0, -1);
		ans += dp[0][1] * mint(1 << t);
	}
	print(ans);
}
0