結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
👑  binap
|
| 提出日時 | 2024-10-12 04:20:25 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 298 ms / 2,000 ms |
| コード長 | 7,090 bytes |
| コンパイル時間 | 4,662 ms |
| コンパイル使用メモリ | 273,292 KB |
| 最終ジャッジ日時 | 2025-02-24 17:24:59 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>#define rep(i,n) for(int i=0;i<n;i++)using namespace std;using namespace atcoder;typedef long long ll;typedef vector<int> vi;typedef vector<long long> vl;typedef vector<vector<int>> vvi;typedef vector<vector<long long>> vvl;typedef long double ld;typedef pair<int, int> P;template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); returnos;}template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : "");return os;}template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){returntrue;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n- 1 ? "\n" : " "); return os;}template<typename T> void chmin(T& a, T b){a = min(a, b);}template<typename T> void chmax(T& a, T b){a = max(a, b);}// Lowest Common Ancestor by binary lifting// https://youtu.be/8uowVvQ_-Mo?t=4306template<typename T=int> // T: type of coststruct lca {int n, root, l;vector<vector<int>> to;vector<vector<T>> co;vector<int> dep;vector<T> costs;vector<vector<int>> par;lca(int n):n(n),to(n),co(n),dep(n),costs(n) {l = 0;while ((1<<l) < n) ++l;par = vector<vector<int>>(n+1,vector<int>(l,n));}void addEdge(int a, int b, T c=0) {to[a].push_back(b); co[a].push_back(c);to[b].push_back(a); co[b].push_back(c);}void dfs(int v, int d=0, T c=0, int p=-1) {if (p != -1) par[v][0] = p;dep[v] = d;costs[v] = c;for (int i = 0; i < to[v].size(); ++i) {int u = to[v][i];if (u == p) continue;dfs(u, d+1, c+co[v][i], v);}}void init(int _root=0) {root = _root;dfs(root);for (int i = 0; i < l-1; ++i) {for (int v = 0; v < n; ++v) {par[v][i+1] = par[par[v][i]][i];}}}// LCAint up(int v, int k) {for (int i = l-1; i >= 0; --i) {int len = 1<<i;if (k >= len) k -= len, v = par[v][i];}return v;}int operator()(int a, int b) {if (dep[a] > dep[b]) swap(a,b);b = up(b, dep[b]-dep[a]);if (a == b) return a;for (int i = l-1; i >= 0; --i) {int na = par[a][i], nb = par[b][i];if (na != nb) a = na, b = nb;}return par[a][0];}int length(int a, int b) {int c = (*this)(a,b);return dep[a]+dep[b]-dep[c]*2;}T dist(int a, int b) {int c = (*this)(a,b);return costs[a]+costs[b]-costs[c]*2;}};using mint = modint1000000007;struct S{mint a, b, c, d;S(mint a = 1, mint b = 0, mint c = 0, mint d = 1) : a(a), b(b), c(c), d(d) {}};S op(S s1, S s2){return S(s1.a * s2.a + s1.b * s2.c, s1.a * s2.b + s1.b * s2.d, s1.c * s2.a + s1.d * s2.c, s1.c * s2.b + s1.d * s2.d);}S e(){return S(1, 0, 0, 1);}int main(){int n;cin >> n;vector<vector<int>> G(n);lca lca_graph(n);vector<pair<int, int>> Edge;rep(i, n - 1){int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);lca_graph.addEdge(u, v);Edge.emplace_back(u, v);}lca_graph.init();vector<vector<int>> children(n);vector<int> sz(n);vector<int> parent(n, -1);auto dfs_sz = [&](auto self, int from, int prev) -> int{int res = 1;for(int to : G[from]){if(to == prev) continue;children[from].push_back(to);parent[to] = from;res += self(self, to, from);}return sz[from] = res;};dfs_sz(dfs_sz, 0, -1);vector<int> belong_major(n, -1);vector<int> belong_minor(n, -1);vector<int> parent_light(n, -1);vector<int> direction_light(n, -1);vector<int> length(n);vector<segtree<S, op, e>> seg;vector<vector<S>> light(n);auto dfs_decompose = [&](auto self, int from, int prev) -> void{sort(children[from].begin(), children[from].end(), [&](int u, int v){return sz[u] > sz[v];});if(children[from].size()){// heavy edge{int to = children[from][0];belong_major[to] = belong_major[from];belong_minor[to] = belong_minor[from] + 1;parent_light[to] = prev;direction_light[to] = direction_light[from];length[belong_major[to]]++;self(self, to, prev);}// light edgefor(int dir = 1; dir < int(children[from].size()); dir++){int to = children[from][dir];belong_major[to] = to;belong_minor[to] = 0;parent_light[to] = from;direction_light[to] = dir;length[belong_major[to]]++;self(self, to, from);}}};belong_major[0] = 0;belong_minor[0] = 0;length[0] = 1;dfs_decompose(dfs_decompose, 0, -1);rep(i, n){int sz_tmp = max(0, length[i] - 1);vector<S> init(sz_tmp, e());seg.emplace_back(init);}rep(i, n){light[i].resize(int(children[i].size()), e());}int q;cin >> q;rep(_, q){char type;cin >> type;if(type == 'g'){int i, j;cin >> i >> j;S s = e();while(belong_major[i] != belong_major[j]){s = op(seg[belong_major[j]].prod(0, belong_minor[j]), s);s = op(light[parent_light[j]][direction_light[j]], s);j = parent_light[j];}s = op(seg[belong_major[i]].prod(belong_minor[i], belong_minor[j]), s);cout << s.a << ' ' << s.b << ' ' << s.c << ' ' << s.d << ' ' << "\n";}if(type == 'x'){int idx;cin >> idx;mint a, b, c, d;cin >> a >> b >> c >> d;S s(a, b, c, d);auto [u, v] = Edge[idx];if(belong_major[u] == belong_major[v]){int pos = min(belong_minor[u], belong_minor[v]);seg[belong_major[u]].set(pos, s);}else{if(parent_light[u] == v){int dir = direction_light[u];light[v][dir] = s;}if(parent_light[v] == u){int dir = direction_light[v];light[u][dir] = s;}}}}return 0;}