QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#338524 | #7997. 树 V 图 | mashduihca | WA | 39ms | 74292kb | C++23 | 10.0kb | 2024-02-26 00:13:10 | 2024-02-26 00:13:10 |
Judging History
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;
详细
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'