結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 anta
|
| 提出日時 | 2015-06-26 22:50:57 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 1,192 ms / 10,000 ms |
| コード長 | 11,613 bytes |
| コンパイル時間 | 1,906 ms |
| コンパイル使用メモリ | 110,272 KB |
| 実行使用メモリ | 34,344 KB |
| 最終ジャッジ日時 | 2024-07-07 18:13:53 |
| 合計ジャッジ時間 | 6,546 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,192 ms
33,392 KB |
| testcase_01 | AC | 756 ms
34,344 KB |
| testcase_02 | AC | 1,092 ms
33,468 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:338:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
338 | rep(i, N) scanf("%d", &S[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:339:32: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
339 | rep(i, N) scanf("%d", &C[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:343:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
343 | scanf("%d%d", &A, &B), -- A, -- B;
| ~~~~~^~~~~~~~~~~~~~~~
main.cpp:360:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
360 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
main.cpp:363:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
363 | scanf("%d", &ty);
| ~~~~~^~~~~~~~~~~
main.cpp:366:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
366 | scanf("%d%d%d", &X, &Y, &Z), -- X, -- Y;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:385:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
385 | scanf("%d%d", &X, &Y), -- X, -- Y;
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
struct CentroidPathDecomposition {
vector<int> colors, positions; //Vertex -> Color, Vertex -> Offset
vector<int> lengths, parents, branches; //Color -> Int, Color -> Color, Color -> Offset
vector<int> parentnodes, depths; //Vertex -> Vertex, Vertex -> Int
//vector<FenwickTree>とかを避けて1次元にしたい時に使う
//sortednodesの[lefts[v], rights[v])はvのsubtreeとなっている
vector<int> sortednodes, offsets; //Index -> Vertex, Color -> Index
vector<int> lefts, rights; //Vertex -> Index
struct BuildDFSState {
int i, len, parent;
BuildDFSState() { }
BuildDFSState(int i_, int l, int p): i(i_), len(l), parent(p) { }
};
//両方の辺があってもいいし、親から子への辺だけでもよい
void build(const vector<vi> &g, int root) {
int n = g.size();
colors.assign(n, -1); positions.assign(n, -1);
lengths.clear(); parents.clear(); branches.clear();
parentnodes.assign(n, -1); depths.assign(n, -1);
sortednodes.clear(); offsets.clear();
lefts.assign(n, -1); rights.assign(n, -1);
vector<int> subtreesizes;
measure(g, root, subtreesizes);
typedef BuildDFSState State;
depths[root] = 0;
vector<State> s;
s.push_back(State(root, 0, -1));
while(!s.empty()) {
State t = s.back(); s.pop_back();
int i = t.i, len = t.len;
int index = sortednodes.size();
int color = lengths.size();
if(t.parent == -3) {
rights[i] = index;
continue;
}
if(t.parent != -2) {
assert(parents.size() == color);
parents.push_back(t.parent);
branches.push_back(len);
offsets.push_back(index);
len = 0;
}
colors[i] = color;
positions[i] = len;
lefts[i] = index;
sortednodes.push_back(i);
int maxsize = -1, maxj = -1;
each(j, g[i]) if(colors[*j] == -1) {
if(maxsize < subtreesizes[*j]) {
maxsize = subtreesizes[*j];
maxj = *j;
}
parentnodes[*j] = i;
depths[*j] = depths[i] + 1;
}
s.push_back(State(i, -1, -3));
if(maxj == -1) {
lengths.push_back(len + 1);
}else {
each(j, g[i]) if(colors[*j] == -1 && *j != maxj)
s.push_back(State(*j, len, color));
s.push_back(State(maxj, len + 1, -2));
}
}
}
void get(int v, int &c, int &p) const {
c = colors[v]; p = positions[v];
}
bool go_up(int &c, int &p) const {
p = branches[c]; c = parents[c];
return c != -1;
}
inline const int *nodesBegin(int c) const { return &sortednodes[0] + offsets[c]; }
inline const int *nodesEnd(int c) const { return &sortednodes[0] + (c+1 == offsets.size() ? sortednodes.size() : offsets[c+1]); }
private:
void measure(const vector<vi> &g, int root, vector<int> &out_subtreesizes) const {
out_subtreesizes.assign(g.size(), -1);
vector<int> s;
s.push_back(root);
while(!s.empty()) {
int i = s.back(); s.pop_back();
if(out_subtreesizes[i] == -2) {
int s = 1;
each(j, g[i]) if(out_subtreesizes[*j] != -2)
s += out_subtreesizes[*j];
out_subtreesizes[i] = s;
}else {
s.push_back(i);
each(j, g[i]) if(out_subtreesizes[*j] == -1)
s.push_back(*j);
out_subtreesizes[i] = -2;
}
}
}
};
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt(): x(0) { }
ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const {
signed a = x, b = MOD, u = 1, v = 0;
while(b) {
signed t = a / b;
a -= t * b; std::swap(a, b);
u -= t * v; std::swap(u, v);
}
if(u < 0) u += Mod;
ModInt res; res.x = (unsigned)u;
return res;
}
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
typedef ModInt<1000000007> mint;
vector<mint> coefs, coefsum;
typedef mint Val;
struct Sum {
mint sum;
Sum() { }
Sum(const Val &val, int pos): sum(val) { }
Sum &operator+=(const Sum &that) { sum += that.sum; return *this; }
Sum operator+(const Sum &that) const { return Sum(*this) += that; }
};
struct Add {
mint add;
Add() { }
Add &operator+=(const Add &that) { add += that.add; return *this; }
void addToVal(Val &val, int pos) const { val += add * coefs[pos]; }
void addToSum(Sum &sum, int left, int right) const { sum.sum += (coefsum[right] - coefsum[left]) * add; }
};
struct SegmentTree {
vector<Val> leafs;
vector<Sum> nodes;
vector<Add> add;
vector<int> leftpos, rightpos;
int n, n2;
void init(int n_, const Val &v = Val()) { init(vector<Val>(n_, v)); }
void init(const vector<Val> &u) {
n = 1; while(n < (int)u.size()) n *= 2;
n2 = (n - 1) / 2 + 1;
leafs = u; leafs.resize(n, Val());
nodes.resize(n);
for(int i = n-1; i >= n2; -- i)
nodes[i] = Sum(leafs[i*2-n], i*2-n) + Sum(leafs[i*2+1-n], i*2+1-n);
for(int i = n2-1; i > 0; -- i)
nodes[i] = nodes[i*2] + nodes[i*2+1];
add.assign(n, Add());
leftpos.resize(n); rightpos.resize(n);
for(int i = n-1; i >= n2; -- i) {
leftpos[i] = i*2-n;
rightpos[i] = (i*2+1-n) + 1;
}
for(int i = n2-1; i > 0; -- i) {
leftpos[i] = leftpos[i*2];
rightpos[i] = rightpos[i*2+1];
}
}
Val get(int i) {
int indices[128];
int k = getIndices(indices, i, i+1);
propagateRange(indices, k);
return leafs[i];
}
Sum getRangeCommutative(int i, int j) {
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(int l = i + n, r = j + n; l < r; l >>= 1, r >>= 1) {
if(l & 1) res += sum(l ++);
if(r & 1) res += sum(-- r);
}
return res;
}
Sum getRange(int i, int j) {
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
Sum res = Sum();
for(; i && i + (i&-i) <= j; i += i&-i)
res += sum((n+i) / (i&-i));
for(k = 0; i < j; j -= j&-j)
indices[k ++] = (n+j) / (j&-j) - 1;
while(-- k >= 0) res += sum(indices[k]);
return res;
}
void set(int i, const Val &x) {
int indices[128];
int k = getIndices(indices, i, i+1);
propagateRange(indices, k);
leafs[i] = x;
mergeRange(indices, k);
}
void addToRange(int i, int j, const Add &x) {
if(i >= j) return;
int indices[128];
int k = getIndices(indices, i, j);
propagateRange(indices, k);
int l = i + n, r = j + n;
if(l & 1) { int p = (l ++) - n; x.addToVal(leafs[p], p); }
if(r & 1) { int p = (-- r) - n; x.addToVal(leafs[p], p); }
for(l >>= 1, r >>= 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) add[l ++] += x;
if(r & 1) add[-- r] += x;
}
mergeRange(indices, k);
}
private:
int getIndices(int indices[], int i, int j) const {
int k = 0, l, r;
if(i >= j) return 0;
for(l = (n + i) >> 1, r = (n + j - 1) >> 1; l != r; l >>= 1, r >>= 1) {
indices[k ++] = l;
indices[k ++] = r;
}
for(; l; l >>= 1) indices[k ++] = l;
return k;
}
void propagateRange(int indices[], int k) {
for(int i = k - 1; i >= 0; -- i)
propagate(indices[i]);
}
void mergeRange(int indices[], int k) {
for(int i = 0; i < k; ++ i)
merge(indices[i]);
}
inline void propagate(int i) {
if(i >= n) return;
add[i].addToSum(nodes[i], leftpos[i], rightpos[i]);
if(i * 2 < n) {
add[i * 2] += add[i];
add[i * 2 + 1] += add[i];
}else {
add[i].addToVal(leafs[i * 2 - n], i * 2 - n);
add[i].addToVal(leafs[i * 2 + 1 - n], i * 2 + 1 - n);
}
add[i] = Add();
}
inline void merge(int i) {
if(i >= n) return;
nodes[i] = sum(i * 2) + sum(i * 2 + 1);
}
inline Sum sum(int i) {
propagate(i);
return i < n ? nodes[i] : Sum(leafs[i - n], i - n);
}
};
int lowest_common_ancestor(const CentroidPathDecomposition &cpd, int x, int y) {
int cx, px, cy, py;
cpd.get(x, cx, px);
cpd.get(y, cy, py);
while(cx != cy) {
if(cpd.depths[*cpd.nodesBegin(cx)] < cpd.depths[*cpd.nodesBegin(cy)])
cpd.go_up(cy, py);
else
cpd.go_up(cx, px);
}
return cpd.nodesBegin(cx)[min(px, py)];
}
int main() {
int N;
while(~scanf("%d", &N)) {
vector<int> S(N), C(N);
rep(i, N) scanf("%d", &S[i]);
rep(i, N) scanf("%d", &C[i]);
vector<vi> g(N);
rep(i, N-1) {
int A, B;
scanf("%d%d", &A, &B), -- A, -- B;
g[A].push_back(B);
g[B].push_back(A);
}
CentroidPathDecomposition cpd; cpd.build(g, 0);
int N2 = N * 2;
coefs.assign(N2, mint());
rep(i, N)
coefs[i] = C[cpd.sortednodes[i]];
coefsum.assign(N2 + 1, mint());
rep(i, N2)
coefsum[i+1] = coefsum[i] + coefs[i];
vector<Val> initval(N);
rep(i, N)
initval[i] = S[cpd.sortednodes[i]];
SegmentTree segt; segt.init(initval);
int Q;
scanf("%d", &Q);
rep(ii, Q) {
int ty;
scanf("%d", &ty);
if(ty == 0) {
int X, Y, Z;
scanf("%d%d%d", &X, &Y, &Z), -- X, -- Y;
Add add; add.add = Z;
int u = X, v = Y;
int w = lowest_common_ancestor(cpd, u, v), wc, wp;
cpd.get(w, wc, wp);
rep(uv, 2) {
int c, p;
cpd.get(uv == 0 ? u : v, c, p);
while(1) {
int top = c == wc ? wp + uv : 0;
int o = cpd.offsets[c], len = cpd.lengths[c];
//ここで[o + top, o + p]で処理する (閉区間！)
segt.addToRange(o + top, o + p + 1, add);
if(c == wc) break;
cpd.go_up(c, p);
}
}
}else {
int X, Y;
scanf("%d%d", &X, &Y), -- X, -- Y;
int u = X, v = Y;
int w = lowest_common_ancestor(cpd, u, v), wc, wp;
cpd.get(w, wc, wp);
Sum sum;
rep(uv, 2) {
int c, p;
cpd.get(uv == 0 ? u : v, c, p);
while(1) {
int top = c == wc ? wp + uv : 0;
int o = cpd.offsets[c], len = cpd.lengths[c];
//ここで[o + top, o + p]で処理する (閉区間！)
sum += segt.getRangeCommutative(o + top, o + p + 1);
if(c == wc) break;
cpd.go_up(c, p);
}
}
mint ans = sum.sum;
printf("%d\n", ans.get());
}
}
}
return 0;
}