結果
| 問題 |
No.235 めぐるはめぐる (5)
|
| コンテスト | |
| ユーザー |
 koyumeishi
|
| 提出日時 | 2015-06-27 01:37:22 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,726 bytes |
| コンパイル時間 | 1,811 ms |
| コンパイル使用メモリ | 114,084 KB |
| 実行使用メモリ | 97,048 KB |
| 最終ジャッジ日時 | 2024-07-07 19:51:07 |
| 合計ジャッジ時間 | 7,412 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 3 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:459:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
459 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
main.cpp:463:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
463 | scanf("%d", &s[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:467:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
467 | scanf("%d", &c[i]);
| ~~~~~^~~~~~~~~~~~~
main.cpp:473:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
473 | scanf("%d%d", &a,&b);
| ~~~~~^~~~~~~~~~~~~~~
main.cpp:482:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
482 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
main.cpp:485:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
485 | scanf("%d", &type);
| ~~~~~^~~~~~~~~~~~~
main.cpp:488:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
488 | scanf("%d%d%d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:495:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
495 | scanf("%d%d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MOD 1000000007
vector<int> s, c;
class LCA{
int root;
//depth of node[i]
vector<int> d;
//parent of node[i]
vector<vector<int> > p;
int log_n;
//initialization of depths and parents
void init(vector<vector<int> > &g, int pos, int last, int v){
d[pos] = v;
p[0][pos] = last;
for(int i=0; i<g[pos].size(); i++){
if(g[pos][i] == last) continue;
init(g, g[pos][i], pos, v+1);
}
}
public:
//vector<vector<int> >
//g[i][j] := node[i]'s edge gose to node[ g[i][j] ]
LCA(vector<vector<int> > &g, int r){
int n = g.size();
root = r;
d = vector<int>(n);
log_n = (log(n)/log(2) + 1);
p = vector<vector<int> >(log_n, vector<int>(n));
init(g, root,-1,0);
for(int k=0; k+1 < log_n; k++){
for(int v=0; v<n; v++){
if(p[k][v] < 0) p[k+1][v] = -1;
else p[k+1][v] = p[k][p[k][v]];
}
}
}
LCA(vector<vector<int> > &g){
int n = g.size();
root = 0;
d = vector<int>(n);
log_n = (log(n)/log(2) + 1);
p = vector<vector<int> >(log_n, vector<int>(n));
//initialize as root = 0
init(g, root,-1,0);
for(int k=0; k+1 < log_n; k++){
for(int v=0; v<n; v++){
if(p[k][v] < 0) p[k+1][v] = -1;
else p[k+1][v] = p[k][p[k][v]];
}
}
}
//return the node number of lowest common ancestor between u and v
int get_lca(int u, int v){
if(d[u] > d[v]) swap(u,v);
for(int k=0; k<log_n; k++){
if( (d[v] - d[u]) >> k & 1){
v = p[k][v];
}
}
if(u==v) return u;
for(int k=log_n-1; k>=0; k--){
if(p[k][u] != p[k][v]) {
u = p[k][u];
v = p[k][v];
}
}
return p[0][u];
}
//return depth of node[u]
int depth(int u){
return d[u];
}
};
struct my_value{
long long c;
long long val;
my_value(): c(0), val(0){
}
my_value(long long c_, long long val_) : c(c_), val(val_){
}
};
template<class T=my_value, class V=long long>
class Segment_Tree_Lazy{
private:
//default values are set in the constractor
const T default_value; //default (NULL) node value
const V default_lazy_value; //default lazy value
struct node{
T value; V lazy_value;
bool lazy; int lb; int ub;
node* par; node* lch; node* rch;
node(T default_value, V default_lazy_value) :
value(default_value),
lazy_value(default_lazy_value),
lazy(false),
lb(0),ub(0),
par(NULL),lch(NULL),rch(NULL){
}
};
T evaluate(T left_val, T right_val){
return my_value((left_val.c, right_val.c)%MOD, (left_val.val + right_val.val)%MOD);
}
void new_lazy(node* t, V z){
if(t==NULL) return;
if(t->lazy){
t->lazy_value = t->lazy_value + z;
}else{
t->lazy_value = z;
}
t->lazy = true;
}
T get_value(node* t){
if(t==NULL) return default_value;
if(t->lazy) return T(t->value.c , (t->value.val + (t->lazy_value * t->value.c)) % MOD);
return t->value;
}
vector<node> v;
node* root;
int size;
node* constract(node* t, int pos, int lb, int ub){
if(pos == 0){
t->par = t;
}
t->lb = lb;
t->ub = ub;
if(pos<size-1){
t->lch = constract(&v[(pos<<1) + 1], (pos<<1) + 1, lb, (ub+lb)>>1);
t->lch->par = t;
t->rch = constract(&v[(pos<<1) + 2], (pos<<1) + 2, (ub+lb)>>1, ub);
t->rch->par = t;
}
return t;
}
void initialize(int size_){
size = 1;
while(size < size_) size <<= 1;
v = vector<node>(size<<1, node(default_value, default_lazy_value));
root = constract(&v[0], 0, 0, size);
}
//propagate lazy value of node t to its children
void push(node* t){
if(t==NULL) return;
if(t->lazy){
if(t->lch != NULL){ //has child
new_lazy(t->lch, t->lazy_value);
new_lazy(t->rch, t->lazy_value);
t->value = evaluate( get_value(t->lch), get_value(t->rch) );
}else{
t->value = get_value(t);
}
t->lazy_value = default_lazy_value;
t->lazy = false;
}
}
void range_add(int left, int right, V z, node* t){
if(t==NULL) return;
if(t->ub <= left || right <= t->lb){
return;
}
push(t);
if(left <= t->lb && t->ub <= right){
new_lazy(t, z);
return;
}
//partialy covered
range_add(left, right, z, t->lch);
range_add(left, right, z, t->rch);
t->value = evaluate( get_value(t->lch), get_value(t->rch) );
}
//get value of [left,right)
T get_range_value(int left, int right, node* t){
if(t==NULL) return default_value;
if(t->ub <= left || right <= t->lb){
return default_value;
}
push(t);
if(left <= t->lb && t->ub <= right){
return get_value(t);
}
T L = get_range_value(left, right, t->lch);
T R = get_range_value(left, right, t->rch);
return evaluate(L, R);
}
public:
//default node value must be set
// sum : 0
// max : MIN_INF
// min : MAX_INF
// gcd : 1
Segment_Tree_Lazy(int size_) :
default_value(T()), default_lazy_value(0LL){
initialize(size_);
}
Segment_Tree_Lazy() :
default_value(T()), default_lazy_value(0LL){
}
void resize(int sz){
initialize(sz);
}
//node[pos] <= new_value
void update(int pos, T new_value){
node* t = &v[pos + size-1];
t->value = new_value;
while(t != root){
t = t->par;
t->value = evaluate( get_value(t->lch), get_value(t->rch) );
}
}
//[l,r) += add_value
void range_add(int left, int right, V z){
range_add(left, right, z, root);
}
//get value [left,right)
T get_range_value(int left, int right){
return get_range_value(left, right, root);
}
void dbg(){
for(int i=0; i<v.size(); i++){
cerr << get_value(&v[i]) << " ";
}
cerr << endl;
}
};
class HL_Decomposition{
class decomposited_node{
public:
Segment_Tree_Lazy<my_value, long long> seg;
int size;
int root;
decomposited_node(){}
decomposited_node(int size_, int root_) :
seg(size_), size(size_), root(root_){
}
};
class info{
public:
decomposited_node* node;
int pos;
info():node(NULL){}
};
int sub_tree_dfs(int pos, int par){
parent[pos] = par;
int ret = 1;
for(int i=0; i<G[pos].size(); i++){
int to = G[pos][i];
if(to == par) continue;
ret += sub_tree_dfs(to, pos);
}
sub_tree_size[pos] = ret;
return ret;
}
public:
int n;
vector<vector<int>> G;
vector<int> parent;
vector<int> sub_tree_size;
vector<info> information;
vector<vector<int>> decomposited_tree;
vector<decomposited_node> dec_nodes;
LCA lca;
HL_Decomposition(vector<vector<int>>& G, int root = 0) :
n(G.size()), sub_tree_size(G.size()), information(G.size()), lca(G,root), parent(G.size()){
this->G = G;
sub_tree_dfs(0,0);
vector<bool> visit(n, false);
queue<int> head;
head.push(0);
while(head.size()){
int pos = head.front();
decomposited_tree.push_back({pos});
head.pop();
visit[pos] = true;
while(true){
int max_size = 0;
int next = -1;
for(int i=0; i<G[pos].size(); i++){
int to = G[pos][i];
if(visit[to]) continue;
if(max_size < sub_tree_size[to]){
if(next>=0){
head.push(next);
}
max_size = sub_tree_size[to];
next = to;
}else{
head.push(to);
}
}
if(next < 0) break;
decomposited_tree.back().push_back(next);
visit[next] = true;
pos = next;
}
}
dec_nodes.resize(decomposited_tree.size());
for(int i=0; i<decomposited_tree.size(); i++){
dec_nodes[i].size = decomposited_tree[i].size();
dec_nodes[i].root = decomposited_tree[i][0];
dec_nodes[i].seg.resize(dec_nodes[i].size);
for(int j=0; j<decomposited_tree[i].size(); j++){
int pos = decomposited_tree[i][j];
information[pos].node = &dec_nodes[i];
information[pos].pos = j;
dec_nodes[i].seg.update(j, my_value(c[pos], s[pos]));
//cerr <<"{ " << c[pos] << ", " << s[pos] << " }, ";
}
//cerr << endl;
}
}
long long query_get_val(int pos, int lca_, int type){
decomposited_node* t = information[pos].node;
if(t != information[lca_].node){
long long ret = 0;
int l = 0;
int r = information[pos].pos+1;
ret = t->seg.get_range_value(l, r).val;
ret += query_get_val(parent[t->root], lca_, type);
ret %= MOD;
return ret;
}else{
int l = information[lca_].pos;
int r = information[pos].pos+1;
if(type == 1) l += 1;
return t->seg.get_range_value(l, r).val;
}
}
long long query_get(int x, int y){
int lca_ = lca.get_lca(x,y);
long long ret = 0;
ret += query_get_val(x, lca_, 0);
ret += query_get_val(y, lca_, 1);
ret %= MOD;
return ret;
}
void query_set_val(int pos, int lca_, int type, long long z){
decomposited_node* t = information[pos].node;
if(t != information[lca_].node){
int l = 0;
int r = information[pos].pos+1;
t->seg.range_add(l, r, z);
query_set_val(parent[t->root], lca_, type, z);
}else{
int l = information[lca_].pos;
int r = information[pos].pos+1;
if(type == 1) l += 1;
t->seg.range_add(l, r, z);
}
}
void query_set(int x, int y, long long z){
int lca_ = lca.get_lca(x,y);
query_set_val(x, lca_, 0, z);
query_set_val(y, lca_, 1, z);
}
};
int main(){
int n;
scanf("%d", &n);
s.resize(n);
c.resize(n);
for(int i=0; i<n; i++){
scanf("%d", &s[i]);
}
for(int i=0; i<n; i++){
scanf("%d", &c[i]);
}
vector<vector<int>> G(n);
for(int i=0; i<n-1; i++){
int a,b;
scanf("%d%d", &a,&b);
a--;b--;
G[a].push_back(b);
G[b].push_back(a);
}
HL_Decomposition hld(G, 0);
int q;
scanf("%d", &q);
while(q--){
int type;
scanf("%d", &type);
if(type == 0){
int x,y,z;
scanf("%d%d%d", &x, &y, &z);
x--;
y--;
hld.query_set(x,y,z);
}else if(type == 1){
int x,y;
scanf("%d%d", &x, &y);
x--;
y--;
long long val = hld.query_get(x,y)%MOD;
printf("%lld\n", val);
}
}
return 0;
}