結果
| 問題 |
No.235 めぐるはめぐる (5)
|
| コンテスト | |
| ユーザー |
 uwi
|
| 提出日時 | 2015-06-27 01:56:37 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,347 ms / 10,000 ms |
| コード長 | 11,491 bytes |
| コンパイル時間 | 4,421 ms |
| コンパイル使用メモリ | 88,032 KB |
| 実行使用メモリ | 127,104 KB |
| 最終ジャッジ日時 | 2024-07-07 19:51:55 |
| 合計ジャッジ時間 | 13,234 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 |
ソースコード
package q5xx;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
// 1:13
public class Q640 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni();
long[] s = new long[n];
long[] c = new long[n];
for(int i = 0;i < n;i++)s[i] = ni();
for(int i = 0;i < n;i++)c[i] = ni();
int[] from = new int[n - 1];
int[] to = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
from[i] = ni() - 1;
to[i] = ni() - 1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] par = pars[0], ord = pars[1], dep = pars[2];
int[] clus = decomposeToHeavyLight(g, par, ord);
int[][] cluspath = clusPaths(clus, ord);
int[] clusiind = clusIInd(cluspath, n);
long[] rs = new long[n];
for(int i = 0;i < n;i++){
int cur = ord[i];
rs[cur] += s[cur];
if(i > 0){
rs[cur] += rs[par[cur]];
if (rs[cur] >= mod)
rs[cur] -= mod;
}
}
int m = cluspath.length;
long[][] cums = new long[m][];
long[][] fts0 = new long[m][];
long[][] fts1 = new long[m][];
for(int i = 0;i < m;i++){
fts0[i] = new long[cluspath[i].length+1];
fts1[i] = new long[cluspath[i].length+1];
cums[i] = new long[cluspath[i].length+1];
for(int j = 0;j < cluspath[i].length;j++){
cums[i][j+1] = cums[i][j] + c[cluspath[i][j]];
if (cums[i][j+1] >= mod)
cums[i][j+1] -= mod;
}
}
int[][] spar = logstepParents(par);
// a a+b a+b+c a+b+c+d
// a b c d
// 0 0 3c 3(c+d)
//
// 3(a+b+c)
for(int Q = ni();Q >= 1;Q--){
int t = ni();
if(t == 0){
// tr();
int x = ni()-1, y = ni()-1, z = ni();
int lca = lca2(x, y, spar, dep);
{
int cx = clus[x]; // クラスタ
int ind = clusiind[x]; // クラスタ内での位置
while (cx != clus[lca]) {
addFenwick(fts1[cx], 0, z);
addFenwick(fts1[cx], ind+1, -z);
addFenwick(fts0[cx], ind+1, cums[cx][ind+1]*z);
int con = par[cluspath[cx][0]];
ind = clusiind[con];
cx = clus[con];
}
addFenwick(fts0[cx], clusiind[lca], -z*cums[cx][clusiind[lca]]);
addFenwick(fts0[cx], ind+1, z*cums[cx][ind+1]);
addFenwick(fts1[cx], clusiind[lca], z);
addFenwick(fts1[cx], ind+1, -z);
}
{
int cx = clus[y]; // クラスタ
int ind = clusiind[y]; // クラスタ内での位置
while (cx != clus[lca]) {
addFenwick(fts1[cx], 0, z);
addFenwick(fts1[cx], ind+1, -z);
addFenwick(fts0[cx], ind+1, cums[cx][ind+1]*z);
int con = par[cluspath[cx][0]];
ind = clusiind[con];
cx = clus[con];
}
addFenwick(fts0[cx], clusiind[lca], -z*cums[cx][clusiind[lca]]);
addFenwick(fts0[cx], ind+1, z*cums[cx][ind+1]);
addFenwick(fts1[cx], clusiind[lca], z);
addFenwick(fts1[cx], ind+1, -z);
}
addFenwick(fts0[clus[lca]], clusiind[lca], z*cums[clus[lca]][clusiind[lca]]);
addFenwick(fts0[clus[lca]], clusiind[lca]+1, -z*cums[clus[lca]][clusiind[lca]+1]);
addFenwick(fts1[clus[lca]], clusiind[lca], -z);
addFenwick(fts1[clus[lca]], clusiind[lca]+1, z);
// for(int j = 0;j < m;j++){
// tr(restoreFenwick(fts0[j]));
// tr(restoreFenwick(fts1[j]));
// }
}else if(t == 1){
int x = ni()-1, y = ni()-1;
int lca = lca2(x, y, spar, dep);
long ret = rs[x] + rs[y] - 2*rs[lca] + s[lca];
long co = 0;
{
int cx = clus[x]; // クラスタ
int ind = clusiind[x]; // クラスタ内での位置
while (cx != clus[lca]) {
co += sumFenwick(fts0[cx], ind);
co += sumFenwick(fts1[cx], ind)*cums[cx][ind+1];
co %= mod;
int con = par[cluspath[cx][0]];
ind = clusiind[con];
cx = clus[con];
}
co += sumFenwick(fts0[cx], ind);
co -= sumFenwick(fts0[cx], clusiind[lca]-1);
co += sumFenwick(fts1[cx], ind) * cums[cx][ind+1];
co -= sumFenwick(fts1[cx], clusiind[lca]-1)*cums[cx][clusiind[lca]];
co %= mod;
}
{
int cx = clus[y]; // クラスタ
int ind = clusiind[y]; // クラスタ内での位置
while (cx != clus[lca]) {
co += sumFenwick(fts0[cx], ind);
co += sumFenwick(fts1[cx], ind)*cums[cx][ind+1];
co %= mod;
int con = par[cluspath[cx][0]];
ind = clusiind[con];
cx = clus[con];
}
co += sumFenwick(fts0[cx], ind);
co -= sumFenwick(fts0[cx], clusiind[lca]-1);
co += sumFenwick(fts1[cx], ind) * cums[cx][ind+1];
co -= sumFenwick(fts1[cx], clusiind[lca]-1)*cums[cx][clusiind[lca]];
co %= mod;
}
co -= sumFenwick(fts0[clus[lca]], clusiind[lca]);
co += sumFenwick(fts0[clus[lca]], clusiind[lca]-1);
co -= sumFenwick(fts1[clus[lca]], clusiind[lca]) * cums[clus[lca]][clusiind[lca]+1];
co += sumFenwick(fts1[clus[lca]], clusiind[lca]-1)*cums[clus[lca]][clusiind[lca]];
co %= mod;
ret += co;
ret %= mod;
if(ret < 0)ret += mod;
out.println(ret);
}else{
throw new RuntimeException();
}
}
}
public static long[] restoreFenwick(long[] ft)
{
int n = ft.length-1;
long[] ret = new long[n];
for(int i = 0;i < n;i++)ret[i] = sumFenwick(ft, i);
for(int i = n-1;i >= 1;i--){
ret[i] -= ret[i-1];
if(ret[i] < 0)ret[i] += mod;
}
return ret;
}
public static int lca2(int a, int b, int[][] spar, int[] depth) {
if (depth[a] < depth[b]) {
b = ancestor(b, depth[b] - depth[a], spar);
} else if (depth[a] > depth[b]) {
a = ancestor(a, depth[a] - depth[b], spar);
}
if (a == b)
return a;
int sa = a, sb = b;
for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
.numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
if ((low ^ high) >= t) {
if (spar[k][sa] != spar[k][sb]) {
low |= t;
sa = spar[k][sa];
sb = spar[k][sb];
} else {
high = low | t - 1;
}
}
}
return spar[0][sa];
}
protected static int ancestor(int a, int m, int[][] spar) {
for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
if ((m & 1) == 1)
a = spar[i][a];
}
return a;
}
public static int[][] logstepParents(int[] par) {
int n = par.length;
int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
int[][] pars = new int[m][n];
pars[0] = par;
for (int j = 1; j < m; j++) {
for (int i = 0; i < n; i++) {
pars[j][i] = pars[j - 1][i] == -1 ? -1
: pars[j - 1][pars[j - 1][i]];
}
}
return pars;
}
public static final int mod = 1000000007;
public static long sumFenwick(long[] ft, int i)
{
long sum = 0;
for(i++;i > 0;i -= i&-i){
sum += ft[i];
if(sum >= mod)sum -= mod;
}
return sum;
}
public static void addFenwick(long[] ft, int i, long v)
{
v %= mod;
if(v < 0)v += mod;
if(v == 0)return;
int n = ft.length;
for(i++;i < n;i += i&-i){
ft[i] += v;
if(ft[i] >= mod)ft[i] -= mod;
}
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static int[] decomposeToHeavyLight(int[][] g, int[] par, int[] ord) {
int n = g.length;
int[] size = new int[n];
Arrays.fill(size, 1);
for (int i = n - 1; i > 0; i--)
size[par[ord[i]]] += size[ord[i]];
int[] clus = new int[n];
Arrays.fill(clus, -1);
int p = 0;
outer: for (int i = 0; i < n; i++) {
int u = ord[i];
if (clus[u] == -1)
clus[u] = p++;
for (int v : g[u]) {
if (par[u] != v && size[v] >= size[u] / 2) {
clus[v] = clus[u];
continue outer;
}
}
for (int v : g[u]) {
if (par[u] != v) {
clus[v] = clus[u];
break;
}
}
}
return clus;
}
public static int[][] clusPaths(int[] clus, int[] ord) {
int n = clus.length;
int[] rp = new int[n];
int sup = 0;
for (int i = 0; i < n; i++) {
rp[clus[i]]++;
sup = Math.max(sup, clus[i]);
}
sup++;
int[][] row = new int[sup][];
for (int i = 0; i < sup; i++)
row[i] = new int[rp[i]];
for (int i = n - 1; i >= 0; i--) {
row[clus[ord[i]]][--rp[clus[ord[i]]]] = ord[i];
}
return row;
}
public static int[] clusIInd(int[][] clusPath, int n) {
int[] iind = new int[n];
for (int[] path : clusPath) {
for (int i = 0; i < path.length; i++) {
iind[path[i]] = i;
}
}
return iind;
}
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 Q640().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))){ // when nextLine, (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)); }
}