結果

問題 No.3249 AND
ユーザー cho435
提出日時 2025-08-30 01:13:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 6,393 bytes
コンパイル時間 4,148 ms
コンパイル使用メモリ 268,528 KB
実行使用メモリ 42,356 KB
最終ジャッジ日時 2025-08-30 01:13:34
合計ジャッジ時間 8,684 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other WA * 1 RE * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)

template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct io_setup {
	io_setup() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(15);
	}
} io_setup;

// https://nyaannyaan.github.io/library/tree/dsu-on-tree.hpp.html
#line 2 "tree/dsu-on-tree.hpp"

#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
	int src, to;
	T cost;

	edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {
	}
	edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {
	}

	edge& operator=(const int& x) {
		to = x;
		return *this;
	}

	operator int() const {
		return to;
	}
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N,
					  int M = -1,
					  bool is_directed = false,
					  bool is_1origin = true) {
	UnweightedGraph g(N);
	if (M == -1) M = N - 1;
	for (int _ = 0; _ < M; _++) {
		int x, y;
		cin >> x >> y;
		if (is_1origin) x--, y--;
		g[x].push_back(y);
		if (!is_directed) g[y].push_back(x);
	}
	return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N,
						int M = -1,
						bool is_directed = false,
						bool is_1origin = true) {
	WeightedGraph<T> g(N);
	if (M == -1) M = N - 1;
	for (int _ = 0; _ < M; _++) {
		int x, y;
		cin >> x >> y;
		T c;
		cin >> c;
		if (is_1origin) x--, y--;
		g[x].emplace_back(x, y, c);
		if (!is_directed) g[y].emplace_back(y, x, c);
	}
	return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph([[maybe_unused]] int N,
				 int M,
				 int is_weighted = true,
				 bool is_1origin = true) {
	Edges<T> es;
	for (int _ = 0; _ < M; _++) {
		int x, y;
		cin >> x >> y;
		T c;
		if (is_weighted) cin >> c;
		else c = 1;
		if (is_1origin) x--, y--;
		es.emplace_back(x, y, c);
	}
	return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N,
						   int M,
						   T INF,
						   int is_weighted = true,
						   bool is_directed = false,
						   bool is_1origin = true) {
	vector<vector<T>> d(N, vector<T>(N, INF));
	for (int _ = 0; _ < M; _++) {
		int x, y;
		cin >> x >> y;
		T c;
		if (is_weighted) cin >> c;
		else c = 1;
		if (is_1origin) x--, y--;
		d[x][y] = c;
		if (!is_directed) d[y][x] = c;
	}
	return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 6 "tree/dsu-on-tree.hpp"

template <typename G>
struct DSUonTree {
   private:
	G& g;
	int N;
	vector<int> sub_sz, euler, down, up;
	int idx_;
	int root;

	int dfs1(int cur, int par = -1) {
		sub_sz[cur] = 1;
		if ((int)g[cur].size() >= 2 and g[cur][0] == par) {
			swap(g[cur][0], g[cur][1]);
		}
		for (auto& dst : g[cur]) {
			if (dst == par) continue;
			sub_sz[cur] += dfs1(dst, cur);
			if (sub_sz[dst] > sub_sz[g[cur][0]]) swap(dst, g[cur][0]);
		}
		return sub_sz[cur];
	}

	void dfs2(int cur, int par = -1) {
		euler[idx_] = cur;
		down[cur] = idx_++;
		for (auto& dst : g[cur]) {
			if (dst == par) continue;
			dfs2(dst, cur);
		}
		up[cur] = idx_;
	}

   public:
	DSUonTree(G& _g, int _root = 0)
		: g(_g),
		  N(_g.size()),
		  sub_sz(_g.size()),
		  euler(_g.size()),
		  down(_g.size()),
		  up(_g.size()),
		  idx_(0),
		  root(_root) {
		dfs1(root);
		dfs2(root);
	}

	int idx(int u) const {
		return down[u];
	}

	template <typename UPDATE, typename QUERY, typename CLEAR, typename RESET>
	void run(UPDATE& update, QUERY& query, CLEAR& clear, RESET& reset) {
		auto dsu = [&](auto rc, int cur, int par = -1,
					   bool keep = false) -> void {
			for (int i = 1; i < (int)g[cur].size(); i++)
				if (g[cur][i] != par) rc(rc, g[cur][i], cur, false);
			if (sub_sz[cur] != 1) rc(rc, g[cur][0], cur, true);
			if (sub_sz[cur] != 1)
				for (int i = up[g[cur][0]]; i < up[cur]; i++) update(euler[i]);
			update(cur);
			query(cur);
			if (!keep) {
				for (int i = down[cur]; i < up[cur]; i++) clear(euler[i]);
				reset();
			}
			return;
		};
		dsu(dsu, root);
	}
};

/**
 * @brief DSU on Tree(Guni)
 * @docs docs/tree/dsu-on-tree.md
 */

namespace cho {

std::vector<int> prime_table(int n) {
	std::vector<int> p(n + 1, -1);
	for (int i = 2; i * i <= n; i++) {
		if (p[i] != -1) continue;
		for (int j = i * i; j <= n; j += i) {
			p[j] = i;
		}
	}
	return p;
}

std::map<int, int> table_factor(int n) {
	const static std::vector<int> table = prime_table(1e7);
	assert(n <= 1e7);
	std::map<int, int> res;
	while (n > 1) {
		if (table[n] == -1) {
			res[n]++;
			break;
		}
		res[table[n]]++;
		n /= table[n];
	}
	return res;
}

}  // namespace cho

#include <atcoder/all>
using mint = atcoder::modint998244353;

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, 0, n) cin >> a[i];
	auto g = graph(n);
	vector<vector<array<int, 2>>> dda(n);
	rep(i, 0, n) {
		auto mp = cho::table_factor(a[i]);
		vector<array<int, 2>> vp;
		dda[i].reserve(mp.size());
		for (auto [k, x] : mp) dda[i].push_back({k, x});
	}
	map<int, int> mp;
	mint ans = 1;
	vector<mint> vans(n);
	// reflect data of node i
	auto update = [&](int i) {
		for (auto [val, x] : dda[i]) {
			ans *= mint(val).pow(x - mp[val]);
			mp[val] = x;
		}
	};
	// answer queries of subtree i
	auto query = [&](int i) {
		vans[i] = ans;
	};
	// below two function are called if all data must be deleted
	// delete data of node i (if necesarry)
	auto clear = [&](int i) {
		// for (auto [val, x] : dda[i]) {
		// 	auto itr = mp.find(val);
		// 	if (itr->second.size() == 1) {
		// 		mp.erase(itr);
		// 		ans /= mint(val).pow(x);
		// 	} else {
		// 		auto itr2 = itr->second.find(x);
		// 		if (next(itr2) == itr->second.end()) {
		// 			itr->second.erase(itr2);
		// 			ans /= mint(val).pow(x - *itr->second.rbegin());
		// 		} else {
		// 			itr->second.erase(itr2);
		// 		}
		// 	}
		// }
	};
	// delete data related to all (if necesarry)
	auto reset = [&]() {
		mp.clear();
		ans = 1;
	};
	DSUonTree<decltype(g)> dsu(g, 0);
	dsu.run(update, query, clear, reset);
	rep(i, 0, n) cout << vans[i].val() << "\n";
}

int main() {
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0