結果
| 問題 |
No.650 行列木クエリ
|
| コンテスト | |
| ユーザー |
 tanzaku
|
| 提出日時 | 2017-04-09 13:06:08 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 689 ms / 2,000 ms |
| コード長 | 10,078 bytes |
| コンパイル時間 | 5,843 ms |
| コンパイル使用メモリ | 87,736 KB |
| 実行使用メモリ | 73,388 KB |
| 最終ジャッジ日時 | 2024-10-09 08:53:23 |
| 合計ジャッジ時間 | 9,430 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 10 |
ソースコード
import java.io.*;
import java.util.*;
public class _p1317_Validate {
public static void main(String[] args) throws IOException {
new _p1317_Validate().solve();
}
static int mod = (int)1e9+7;
void solve() throws IOException {
try (final InputValidator in = new InputValidator(System.in)) {
int n = in.nextInt(1, 100000);
tree = new HeavyLightDecomposition(n);
in.newLine();
UnionFind uf = new UnionFind(n);
int[][] es = new int[n-1][];
for (int i = 0; i < n - 1; i++) {
int a = in.nextInt(0, n - 1);
in.space();
int b = in.nextInt(0, n - 1);
in.newLine();
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 = in.nextInt(1, 20000);
in.newLine();
while (q-- > 0) {
char c = in.nextChar();
in.space();
if (c == 'x') {
int i = in.nextInt(0, n - 2); in.space();
int x00 = in.nextInt(0, 1000); in.space();
int x01 = in.nextInt(0, 1000); in.space();
int x10 = in.nextInt(0, 1000); in.space();
int x11 = in.nextInt(0, 1000); in.newLine();
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 = in.nextInt(0, n - 1); in.space();
int v = in.nextInt(0, n - 1); in.newLine();
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);
}
System.out.println(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]);
} else {
throw new RuntimeException();
}
}
in.eof();
}
}
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;
}
}
}
}
// for debug
static void dump(Object... o) {
System.err.println(Arrays.deepToString(o));
}
static class InputValidator implements Closeable {
final InputStream in;
final int NO_BUFFER = -2;
int buffer;
public InputValidator(final InputStream in) {
this.in = in;
buffer = NO_BUFFER;
}
public char nextChar() throws IOException {
int res = read();
check(Character.isLetterOrDigit(res));
return (char)res;
}
int read() throws IOException {
final int res = buffer == NO_BUFFER ? in.read() : buffer;
buffer = NO_BUFFER;
return res;
}
void unread(int ch) throws IOException {
buffer = ch;
}
// [low, high]
long nextLong(long low, long high) throws IOException {
long val = 0;
int ch = -1;
boolean read = false;
while (true) {
ch = read();
if (!Character.isDigit(ch)) break;
read = true;
val = val * 10 + ch - '0';
check(val <= high);
}
check(read);
check(ch >= 0);
check(val >= low);
unread(ch);
return val;
}
int nextInt(int low, int high) throws IOException { return (int)nextLong(low, high); }
int[] nextInts(int n, int low, int high) throws IOException {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt(low, high);
if (i + 1 != n) space();
}
newLineOrEOF();
return res;
}
void space() throws IOException { int ch = read(); check(ch == ' '); }
void newLine() throws IOException {
int ch = read();
if (ch == '\r') ch = read();
check(ch == '\n');
}
void newLineOrEOF() throws IOException { int ch = read(); check(ch == '\r' || ch == '\n' || ch < 0); }
void eof() throws IOException { int ch = read(); check(ch < 0); }
void check(boolean b) { if (!b) throw new RuntimeException(); }
@Override
public void close() throws IOException {
}
}
}