結果

問題 No.3250 最小公倍数
ユーザー cho435
提出日時 2025-08-29 23:22:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,211 bytes
コンパイル時間 8,487 ms
コンパイル使用メモリ 399,740 KB
実行使用メモリ 25,472 KB
最終ジャッジ日時 2025-08-29 23:22:51
合計ジャッジ時間 11,892 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 16
権限があれば一括ダウンロードができます

ソースコード

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
 */

// Bint
#include <boost/multiprecision/cpp_int.hpp>
using Bint = boost::multiprecision::cpp_int;

Bint gcd(Bint a, Bint b) {
	while (b > 0) {
		auto c = b;
		b = a % b;
		a = c;
	}
	return a;
}

void solve() {
	int n;
	cin >> n;
	vector<int> a(n);
	rep(i, 0, n) cin >> a[i];
	auto g = graph(n);
	Bint ans = 1;
	vector<int> vans(n);
	// reflect data of node i
	auto update = [&](int i) {
		ans = ans / gcd(ans, a[i]) * a[i];
	};
	// answer queries of subtree i
	auto query = [&](int i) {
		vans[i] = (int)(ans % 998244353);
	};
	auto clear = [&](int i) {
	};
	// delete data related to all (if necesarry)
	auto reset = [&]() {
		ans = 1;
	};
	DSUonTree<decltype(g)> dsu(g, 0);
	dsu.run(update, query, clear, reset);
	rep(i, 0, n) cout << vans[i] << "\n";
}

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