結果
| 問題 |
No.650 行列木クエリ
|
| ユーザー |
 yuya178
|
| 提出日時 | 2018-02-10 15:16:49 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 483 ms / 2,000 ms |
| コード長 | 13,924 bytes |
| コンパイル時間 | 3,739 ms |
| コンパイル使用メモリ | 87,888 KB |
| 実行使用メモリ | 70,472 KB |
| 最終ジャッジ日時 | 2024-10-13 13:06:35 |
| 合計ジャッジ時間 | 6,379 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
import java.io.*;
import java.util.*;
import java.math.*;
// import java.awt.Point;
public class Main {
InputStream is;
PrintWriter out;
String INPUT = "";
static long mod = 1_000_000_007;
int inf = Integer.MAX_VALUE;
void solve(){
int n = ni();
tree = new HeavyLightDecomposition(n);
// UnionFind uf = new UnionFind(n);
int[][] es = new int[n-1][];
for (int i = 0; i < n - 1; i++) {
int a = ni();
int b = ni();
es[i] = new int[]{a,b};
// uf.union(a, b);
tree.addEdge(a, b);
}
tree.init();
seg = new Seg2[tree.getHeavyEdgeCount()];
for (int i = 0; i < seg.length; i++) {
seg[i] = new Seg2(tree.getHeavyEdgeLength(i));
}
for (int[] e : es) {
if (tree.g.childSize[e[0]] < tree.g.childSize[e[1]]) {
int tmp = e[0];
e[0] = e[1];
e[1] = tmp;
}
}
int q = ni();
while (q-- > 0) {
char c = nc();
if (c == 'x') {
int i = ni();
int x00 = ni();
int x01 = ni();
int x10 = ni();
int x11 = ni();
int e = tree.getHeavyEdgeId(es[i][1]);
int j = tree.getIndexInHeavyEdge(es[i][1]);
seg[e].update(j, new long[]{x00,x01,x10,x11});
} else if (c == 'g') {
int u = ni();
int v = ni();
int ei = tree.getHeavyEdgeId(u);
int ej = tree.getHeavyEdgeId(v);
long[] ans = Seg2.id.clone();
while (true) {
int idx = tree.getIndexInHeavyEdge(v);
int left = ei == ej ? tree.getIndexInHeavyEdge(u) + 1 : 0;
ans = Seg2.merge(seg[ej].get(left, idx + 1), ans);
if (ej == ei) break;
v = tree.getParentVertex(ej);
ej = tree.getHeavyEdgeId(v);
}
out.println(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]);
}
}
}
HeavyLightDecomposition tree;
Seg2[] seg;
static class Seg2 {
final int n;
final long[][] seg;
public Seg2(final int n) {
this.n = Integer.highestOneBit(n) << 1;
seg = new long[this.n << 1][];
Arrays.fill(seg, id);
}
static long[] merge(long[] l, long[] r) {
long[] res = new long[4];
res[0] = (l[0] * r[0] + l[1] * r[2]) % mod;
res[1] = (l[0] * r[1] + l[1] * r[3]) % mod;
res[2] = (l[2] * r[0] + l[3] * r[2]) % mod;
res[3] = (l[2] * r[1] + l[3] * r[3]) % mod;
return res;
}
final static long[] id = new long[]{1,0,0,1,};
long[] get(int l, int r) { return get(l, r, 0, 0, n); }
long[] get(int l, int r, int k, int curL, int curR) {
if(curR <= l || curL >= r) return id;
if(l <= curL && curR <= r) { return seg[k]; }
final int curM = (curL + curR) / 2;
return merge(
get(l, r, 2 * k + 1, curL, curM),
get(l, r, 2 * k + 2, curM, curR));
}
void update(int i, long[] v) {
i += n - 1;
seg[i] = v;
while(i != 0) {
i = (i - 1) / 2;
seg[i] = merge(seg[2*i+1], seg[2*i+2]);
}
}
}
static class UnionFind {
private int[] data;
public UnionFind(int size) {
data = new int[size];
clear();
}
public void clear() {
Arrays.fill(data, -1);
}
public int root(int x) { return data[x] < 0 ? x : (data[x] = root(data[x])); }
public void union(int x, int y) {
if((x = root(x)) == (y = root(y))) {
throw new RuntimeException();
}
if(data[y] < data[x]) { final int t = x; x = y; y = t; }
data[x] += data[y];
data[y] = x;
}
public boolean same(int x, int y) { return root(x) == root(y); }
public int size(int x) { return -data[root(x)]; }
}
static public class HeavyLightDecomposition {
final AdjListGraph g;
public HeavyLightDecomposition(final int V) {
g = new AdjListGraph(V, 2 * (V - 1));
}
void addEdge(int s, int t) {
g.addEdge(s, t);
g.addEdge(t, s);
}
int getHeavyEdgeCount() {
return g.heavyEdgeCount;
}
int getHeavyEdgeLength(int heavyEdgeId) {
return g.heavyEdge[heavyEdgeId].length;
}
int getHeavyEdgeDepth(int heavyEdgeId) {
return g.heavyEdgeDepth[heavyEdgeId];
}
int getHeavyEdgeId(int vertexIndex) {
return g.belongHeavyEdgeIndex[vertexIndex];
}
int getIndexInHeavyEdge(int vertexIndex) {
return g.heavyEdgeIndex[vertexIndex];
}
int getParentVertex(int heavyEdgeId) {
return g.heavyEdgeParent[g.heavyEdge[heavyEdgeId][0]];
}
void init() {
g.initHeavyLightDecomposition();
}
static
class AdjListGraph {
int m, V, E;
int[] head, next, to, childSize, parent;
int[] heavyEdgeIndex;
int[] belongHeavyEdgeIndex;
int[] heavyEdgeParent;
int[][] heavyEdge;
int[] heavyEdgeVertexCount;
int[] heavyEdgeDepth;
int heavyEdgeCount;
boolean[] vis;
int[] st;
public AdjListGraph(int V, int E) {
head = new int[V];
childSize = new int[V];
heavyEdgeIndex = new int[V];
belongHeavyEdgeIndex = new int[V];
heavyEdgeVertexCount = new int[V];
heavyEdgeDepth = new int[V];
heavyEdgeParent = new int[V];
parent = new int[V];
next = new int[E];
to = new int[E];
vis = new boolean[head.length];
st = new int[head.length + 1];
this.V = V;
this.E = E;
clear();
}
public void clear() {
m = 0;
Arrays.fill(head, -1);
}
public void addEdge(int s, int t) {
next[m] = head[s];
head[s] = m;
to[m++] = t;
}
public void initHeavyLightDecomposition() {
calcChildSize(0);
initHeavyEdge(0);
}
private void calcChildSize(final int root) {
int sp = 0;
parent[root] = -1;
st[sp++] = root;
while(sp != 0) {
final int v = st[--sp];
if(!vis[v]) {
st[sp++] = v;
childSize[v]++;
vis[v] = true;
for(int e = head[v]; e != -1; e = next[e]) {
final int u = to[e];
if(!vis[u]) {
parent[u] = v;
st[sp++] = u;
}
}
}
else if(parent[v] != -1) {
childSize[parent[v]] += childSize[v];
}
}
}
private void initHeavyEdge(final int root) {
int sp = 0;
st[sp++] = root;
Arrays.fill(vis, false);
heavyEdgeIndex[root] = 0;
belongHeavyEdgeIndex[root] = heavyEdgeCount++;
heavyEdgeParent[root] = -1;
while(sp != 0) {
final int v = st[--sp];
if(!vis[v]) {
st[sp++] = v;
vis[v] = true;
heavyEdgeVertexCount[belongHeavyEdgeIndex[v]]++;
// System.err.println(belongHeavyEdgeIndex[v] + " " + heavyEdgeVertexCount[belongHeavyEdgeIndex[v]]);
int maxChildIndex = -1;
int maxChildSize = 0;
for(int e = head[v]; e != -1; e = next[e]) {
final int u = to[e];
if(!vis[u]) {
if(maxChildSize < childSize[u]) {
maxChildIndex = u;
maxChildSize = childSize[u];
}
// System.err.println(v + " -> " + u + " " + maxChildIndex);
st[sp++] = u;
}
}
for(int e = head[v]; e != -1; e = next[e]) {
final int u = to[e];
if(!vis[u] && maxChildIndex != u) {
heavyEdgeIndex[u] = 0;
heavyEdgeDepth[heavyEdgeCount] = heavyEdgeDepth[belongHeavyEdgeIndex[v]] + 1;
// heavyEdgeVertexCount[heavyEdgeCount] = 1;
belongHeavyEdgeIndex[u] = heavyEdgeCount++;
heavyEdgeParent[u] = v;
}
}
if(maxChildIndex != -1) {
heavyEdgeIndex[maxChildIndex] = heavyEdgeIndex[v] + 1;
belongHeavyEdgeIndex[maxChildIndex] = belongHeavyEdgeIndex[v];
heavyEdgeParent[maxChildIndex] = heavyEdgeParent[v];
}
}
}
heavyEdge = new int[heavyEdgeCount][];
for(int i = 0; i < heavyEdgeCount; i++) {
heavyEdge[i] = new int[heavyEdgeVertexCount[i]];
}
for(int i = 0; i < V; i++) {
final int j = belongHeavyEdgeIndex[i];
// System.err.println(i + " " + j + " " + heavyEdgeIndex[i] + " " + heavyEdge[j].length);
heavyEdge[j][heavyEdgeIndex[i]] = i;
}
}
}
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new Main().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b) && b != ' ')){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}