QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#338524#7997. 树 V 图mashduihcaWA 39ms74292kbC++2310.0kb2024-02-26 00:13:102024-02-26 00:13:10

Judging History

你现在查看的是最新测评结果

  • [2024-02-26 00:13:10]
  • 评测
  • 测评结果：WA
  • 用时：39ms
  • 内存：74292kb
查看
  • [2024-02-26 00:13:10]
  • 提交

answer

bool M1; extern bool M2;
#include <unordered_map>
#include <unordered_set>
#include <type_traits>
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <climits>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <string>
#include <bitset>
#include <random>
#include <chrono>
#include <vector>
#include <cctype>
#include <cstdio>
#include <stack>
#include <array>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <map>
#if __cplusplus > 201703L
#include <ranges>
#include <concepts>
#endif
namespace __xtemp_tools { namespace __xdebugs { template<typename T> inline void _tdebug(const T& x, std::ostream& os); inline void _tdebug(const std::string& s, std::ostream& os); template<typename A, typename B> inline void _tdebug(const std::pair<A, B>& p, std::ostream& os);
#if __cplusplus > 201703L 
	template<typename T> concept osable = requires (const T& x, std::ostream& os) { os << x; }; template<std::ranges::range T> requires (!osable<T>) inline void _tdebug(const T& t, std::ostream& os);
#endif
	template<typename T> inline void _tdebug(const T& x, std::ostream& os) { os << x; } inline void _tdebug(const std::string& s, std::ostream& os) { os << s; } template<typename A, typename B> inline void _tdebug(const std::pair<A, B>& p, std::ostream& os) { os << '{'; _tdebug(p.first, os); os << ','; _tdebug(p.second, os); os << '}'; }
#if __cplusplus > 201703L
	template<std::ranges::range T> requires (!osable<T>) inline void _tdebug(const T& t, std::ostream& os) { os << '{'; for (auto it = t.cbegin(); it != t.cend(); ++it) { if (it != t.cbegin()) os << ','; _tdebug(*it, os); } os << '}'; }
#endif
	template<typename T> inline void _debug(const char* name, const T& x, bool is_constant, std::ostream& os = std::cerr, const char* space = " = ", const char* cutline = "  ") { if (!is_constant) { os << name << space; } _tdebug(x, os); os << cutline; } } }
#define GET_TIME std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now()-__time_start_0).count()
#define LOOK_MEMORY std::cerr << std::setiosflags(std::ios::fixed) << "Memory: " << abs(&M1-&M2)/1024.0/1024.0 << "MB\n";
#define LOOK_TIME std::cerr << "Time: " << GET_TIME << "ms\n";
#define FOR(i,a,b) for(int i=(a),i##end=(b);i<=(i##end);++i)
#define ROF(i,a,b) for(int i=(a),i##end=(b);i>=(i##end);--i)
#define For(i,a,b) for(int i=(a),i##end=(b);i<(i##end);++i)
#define Rof(i,a,b) for(int i=(static_cast<int>(a)-1),i##end=(b);i>=(i##end);--i)
#define rete(e) return [&]()->void{e;}()
#define ALL(x) x.begin(),x.end()
#define var const auto&
#define ret return
#define syt kawaii
#define NAME(x) #x
#define INNAME(x) NAME(x)
#define YES std::cout << "YES\n"
#define Yes std::cout << "Yes\n"
#define No std::cout << "No\n"
#define NO std::cout << "NO\n"
#define rYES return void(YES)
#define rNO return void(NO)
#define rYes return void(Yes)
#define rNo return void(No)
#ifdef LOCAL
#define CONNECT_BASE(x,y) x##y
#define CONNECT(x,y) CONNECT_BASE(x,y)
#define DEBUG_BASE(x) __xtemp_tools::__xdebugs::_debug(NAME(x),x,__builtin_constant_p(x))
#define DEB_1(x) DEBUG_BASE(x)
#define DEB_2(x,y) DEB_1(x) , DEB_1(y)
#define DEB_3(x,y,z) DEB_1(x) , DEB_2(y,z)
#define DEB_4(x,y,z,w) DEB_1(x) , DEB_3(y,z,w)
#define DEB_5(a,b,c,d,e) DEB_1(a) , DEB_4(b,c,d,e)
#define DEB_6(a,b,c,d,e,f) DEB_1(a) , DEB_5(b,c,d,e,f)
#define DEB_7(a,b,c,d,e,f,g) DEB_1(a) , DEB_6(b,c,d,e,f,g)
#define DEB_8(a,b,c,d,e,f,g,h) DEB_1(a) , DEB_7(b,c,d,e,f,g,h)
#define COUNT_BASE(_1,_2,_3,_4,_5,_6,_7,_8,_9,_10,_11,_12,x,...) x
#define COUNT(...) COUNT_BASE(__VA_ARGS__,12,11,10,9,8,7,6,5,4,3,2,1,0)
#define D(...) std::cerr << "[In Line " << __LINE__ << "]: ", CONNECT(DEB_,COUNT(__VA_ARGS__))(__VA_ARGS__) , cerr << '\n'
#define here std::cerr << "here\n";
#define CA std::cerr << "Cut A\n";
#define CE std::cerr << "Cut B\n";
std::chrono::time_point<std::chrono::steady_clock> __time_start_0 = std::chrono::steady_clock::now();
#else
#define D(...) 1
#define here ;
#define CA ;
#define CE ;
#endif
//#define ALWAYS_FLUSH
using ll = long long; using ull = unsigned long long; using Long = __int128_t; using uLong = __uint128_t; using uint = unsigned int; using ull = unsigned long long;
//#define int long long  // here
template<typename A,typename B> inline auto min(const A& x,const B& y) { return x < y ? x : y; } template<typename A,typename B> inline auto max(const A& x,const B& y) { return x > y ? x : y; } template<typename A,typename B,typename... C> inline auto min(const A& x,const B& y,const C&... z) { return ::min(::min(x,y),z...); } template<typename A,typename B,typename... C> inline auto max(const A& x,const B& y,const C&... z){ return ::max(::max(x,y),z...); } using namespace std; inline void untie() { std::cin.tie(nullptr) -> sync_with_stdio(false); } template<typename T,typename... Args> inline void read(T& x,Args&... args); template<typename T> inline void read(T& x); template<typename T> inline void read(std::vector<T>& v); template<typename T,typename... Args> inline void write(const T& x,const Args&... args); template<typename T> inline void write(const T& x); inline void write(); template<typename T> inline void write(const std::vector<T>& v); inline void writesp(); inline void writeln(); template<typename... Args> inline void writeln(const Args&... x); template<typename T,typename... Args> inline void __writeln_base(const T& x,const Args&... args); template<typename T> inline void __writeln_base(const T& x); template<typename T> inline void output(const T& x); template<typename T> inline void output(const std::vector<T>& v); template<typename T> void ckmax(T& x,const T& y) { x = (y > x ? y : x);  } template<typename T> void ckmin(T& x,const T& y) { x = (y < x ? y : x);  } inline int mul(int x,int y); inline int add(int x,int y); inline int del(int x,int y); inline int qpow(int a,int n); inline int inv(int x);
#define MULTY_TEST
using pii = pair<int,int>; using pll = pair<ll,ll>;
mt19937 mt(chrono::high_resolution_clock::now().time_since_epoch().count());
constexpr int mod = 998244353;
constexpr int N = 3005;
int n, m, a[N], dp[N], tmp[N], e[N][N], dis[N][N];
vector<int> g[N];
void get_dis(int p, int fa, int dis[]) {
	for(int x : g[p]) {
		if(x == fa) continue;
		dis[x] = dis[p] + 1;
		get_dis(x, p, dis);
	}
}
void dfs(int p, int fa) {
	for(int x : g[p]) {
		if(x == fa) continue;
		dfs(x, p);
	}
	memset(tmp, 0, sizeof tmp);
	FOR(i,1,n) {
		if(e[a[p]][a[i]]) {
			assert(a[p] != a[i]);
			int x = e[a[p]][a[i]];
			if(dis[p][i] & 1) {
				if(dis[p][x] == dis[x][i] + 1) 
					(tmp[a[i]] += dp[i]) %= mod;
			}
			else {
				if(a[p] < a[i]) {
					if(dis[p][x] == dis[x][i] + 2)
						(tmp[a[i]] += dp[i]) %= mod;
				}
				else {
					if(dis[p][x] == dis[x][i])
						(tmp[a[i]] += dp[i]) %= mod;
				}
			}
		}
	}
	dp[p] = 1;
	FOR(i,1,n) {
		if(e[a[p]][i]) {
			dp[p] = 1LL * dp[p] * tmp[i] % mod;
		}
	}
}
void init(int p, int fa) {
	for(int x : g[p]) {
		if(x == fa) continue;
		if(a[x] != a[p]) e[a[p]][a[x]] = x;
		init(x, p);
	}
}
void mian() {
	memset(e, 0, sizeof e);
	memset(dis, 0, sizeof dis);
	read(n,m);
	FOR(i,1,n) g[i].clear();
	FOR(i,2,n) {
		int x,y;
		read(x,y);
		g[x].push_back(y),
		g[y].push_back(x);
	}
	FOR(i,1,n) {
		read(a[i]);
		get_dis(i, 0, dis[i]);
	}
	init(1, 0);
	dfs(1, 0);
	int ans = 0;
	FOR(i,1,n) if(a[i] == a[1]) (ans += dp[i]) %= mod;
	writeln(ans);
}
void preprocess() {
	
}
/*
  array size.
  mod.
  n and m.
 */
signed main() {
#ifdef FILEIO
	freopen(INNAME(FILEIO)".in","r",stdin) , freopen(INNAME(FILEIO)".out","w",stdout);
#endif
#ifndef LOCAL
	untie();
#endif
	preprocess();
	signed t = 1;
#ifdef MULTY_TEST
	read(t);
#endif
	while(t--)
		mian();
	return 0;
}
#ifdef ALWAYS_FLUSH
#define __FLUSH std::cout << std::flush;
#else
#define __FLUSH ;
#endif
namespace __xtemp_tools {
#ifdef int
	constexpr long long __unit_int = 1;
#else
	constexpr __int128 __unit_int = 1;
#endif
}
inline int mul(int x,int y) { return __xtemp_tools::__unit_int*x*y%mod; } inline int add(int x,int y) { return x+y>=mod?x+y-mod:x+y; } inline int del(int x,int y) { return x-y+mod>=mod?x-y:x+mod-y; } inline int qpow(int a,int n) { int ans = 1; while(n) { if(n & 1) { ans = mul(ans,a); } n >>= 1; a = mul(a,a); } return ans; } inline int inv(int x) { return qpow(x,mod-2); } template<typename T,typename... Args> inline void read(T& x,Args&... args) { read(x),read(args...); } template<typename T> inline void read(T& x) { std::cin >> x; } template<typename T> inline void read(std::vector<T>& v) { for(auto& x : v) read(x); } inline void writesp() { std::cout << ' '; __FLUSH } inline void write() { writesp(); } template<typename T> inline void output(const T& x) { std::cout << x; __FLUSH } template<typename T> inline void output(const std::vector<T>& v) { if(v.empty()) ret ; for(auto it=v.begin();it!=std::prev(v.end());++it) { write(*it); } output(*std::prev(v.end())); } template<typename T> inline void write(const T& x) { output(x), writesp(); } template<typename T,typename... Args> inline void write(const T& x,const Args&... args) { write(x) , write(args...); } template<typename T> inline void write(const std::vector<T>& v) { for(const auto& x : v) write(x); } template<typename T,typename... Args> inline void __writeln_base(const T& x,const Args&... args) { write(x), __writeln_base(args...); } template<typename T> inline void __writeln_base(const T& x) { output(x); } inline void writeln() { std::cout << '\n'; __FLUSH } template<typename... Args> inline void writeln(const Args&... x) { __writeln_base(x...) , std::cout << '\n'; __FLUSH } namespace xtemp { namespace __xtemp_tools { struct __xtemp_noname_for_writeln {}; } } inline void writeln(const xtemp::__xtemp_tools::__xtemp_noname_for_writeln&&) {} inline void write(const xtemp::__xtemp_tools::__xtemp_noname_for_writeln&&) {}
#ifdef LOCAL
__attribute__((constructor)) void __constructor() { } __attribute__((destructor)) void __destructor() { std::cerr << '\n'; LOOK_TIME; LOOK_MEMORY; }
#endif
bool M2;
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 39ms
memory: 74292kb

input:

10
15 2
10 5
3 5
12 5
10 9
11 7
3 8
2 4
7 1
15 14
8 13
15 6
2 1
4 8
11 15
1 1 1 1 2 1 1 1 2 2 1 2 1 1 1
15 3
8 11
12 8
1 3
13 15
5 9
10 13
6 12
14 4
4 9
15 5
11 10
2 14
7 2
6 3
3 2 3 2 2 3 2 1 2 1 1 3 1 2 1
15 5
1 7
5 2
11 9
6 8
13 3
14 12
3 1
8 9
5 10
10 11
5 1
12 13
10 15
11 4
3 3 3 2 3 2 1 2 2 2 ...

output:

11
15
8
9
5
2
4
0
15
18

result:

wrong answer 7th numbers differ - expected: '1', found: '4'
English 繁體中文 简体中文

Server Time: 2024-12-03 22:43:32 | OpenSource Project