結果
| 問題 |
No.650 行列木クエリ
|
| ユーザー |
 yuya178
|
| 提出日時 | 2018-02-10 15:38:17 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 454 ms / 2,000 ms |
| コード長 | 13,321 bytes |
| コンパイル時間 | 2,445 ms |
| コンパイル使用メモリ | 87,528 KB |
| 実行使用メモリ | 70,524 KB |
| 最終ジャッジ日時 | 2024-10-13 14:17:36 |
| 合計ジャッジ時間 | 6,078 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / 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);
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};
tree.addEdge(a, b);
}
tree.init();
SegmentTree[] seg = new SegmentTree[tree.getHeavyEdgeCount()];
for (int i = 0; i < seg.length; i++) {
seg[i] = new SegmentTree(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 = new long[]{1,0,0,1};
while (true) {
int idx = tree.getIndexInHeavyEdge(v);
int left = ei == ej ? tree.getIndexInHeavyEdge(u) + 1 : 0;
long[] res = seg[ej].query(left, idx+1);
ans = comb(res, ans);
if (ej == ei) break;
v = tree.getParentVertex(ej);
ej = tree.getHeavyEdgeId(v);
}
out.println(ans[0] + " " + ans[1] + " " + ans[2] + " " + ans[3]);
}
}
}
long[] comb(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;
}
HeavyLightDecomposition tree;
class SegmentTree {
int n;
long[][] seg;
long[] id = new long[]{1,0,0,1};
SegmentTree(int n) {
this.n = Integer.highestOneBit(n) << 1;
this.seg = new long[this.n<<1][];
Arrays.fill(seg,id);
}
long[] comb(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;
}
void update(int x, long[] value) {
x += n - 1;
this.seg[x] = value;
while (x > 0) {
x = (x - 1) / 2;
this.seg[x] = comb(this.seg[2 * x + 1], this.seg[2 * x + 2]);
}
}
long[] query(int a,int b,int l,int r,int k){
if(a<=l&&r<=b) return seg[k];
if(b<=l||r<=a) return id;
long[] ans1=query(a,b,l,(l+r)/2,2*k+1);
long[] ans2=query(a,b,(l+r)/2,r,2*k+2);
return comb(ans1, ans2);
}
long[] query(int l, int r) {
return query(l,r,0,n,0);
}
}
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)); }
}