結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 kopricky
|
| 提出日時 | 2017-11-18 21:41:42 |
| 言語 | C++11 (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 943 ms / 10,000 ms |
| コード長 | 8,188 bytes |
| コンパイル時間 | 1,790 ms |
| コンパイル使用メモリ | 182,540 KB |
| 実行使用メモリ | 30,272 KB |
| 最終ジャッジ日時 | 2024-11-25 11:59:18 |
| 合計ジャッジ時間 | 5,898 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 3 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:252:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
252 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
main.cpp:255:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
255 | scanf("%d",&s[i]);
| ~~~~~^~~~~~~~~~~~
main.cpp:258:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
258 | scanf("%d",&c[i]);
| ~~~~~^~~~~~~~~~~~
main.cpp:263:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
263 | scanf("%d%d",&a,&b);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:268:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
268 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
main.cpp:277:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
277 | scanf("%d%d%d",&p,&q,&r);
| ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:281:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
281 | scanf("%d",&s);
| ~~~~~^~~~~~~~~
ソースコード
#include <bits/stdc++.h>#define ll long long#define INF 1000000005#define MOD 1000000007#define EPS 1e-10#define rep(i,n) for(int i=0;i<(int)(n);++i)#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)#define each(a,b) for(auto (a): (b))#define all(v) (v).begin(),(v).end()#define len(v) (int)(v).size()#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())#define cmx(x,y) x=max(x,y)#define cmn(x,y) x=min(x,y)#define fi first#define se second#define pb push_back#define show(x) cout<<#x<<" = "<<(x)<<endl#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endlusing namespace std;typedef pair<int,int> P;typedef pair<ll,ll> pll;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<ll> vl;typedef vector<vl> vvl;typedef vector<double> vd;typedef vector<P> vp;typedef vector<string> vs;struct HLdecomposition{struct Centroid{int parid, pardepth, depth, sz; //親のパスのid,親のノードは親のパスの何番目,パスの深さ,属する頂点の数Centroid(int idx, int dep, int deep, int size) : parid(idx), pardepth(dep), depth(deep), sz(size){}inline P Up(){return P(parid, pardepth);}};vector<vector<int> > G;vector<int> stsize, nxpath;vector<int> pathorder, pathid; //何番目のパスに属するか,そのパスの何番目かvector<Centroid> centroids; //パスが格納vector<int> index;void Buildstsize(){stack<P> s;s.push(P(0, -1));while(!s.empty()) {P p = s.top();s.pop();if(stsize[p.first] != -1){nxpath[p.first] = -1;for(int to : G[p.first]){//親に向かう場合if(p.second == to){continue;}stsize[p.first] += stsize[to];if(nxpath[p.first] == -1 || stsize[nxpath[p.first]] < stsize[to]) {nxpath[p.first] = to;}}}else{s.push(p);stsize[p.first] = 1;for(int to : G[p.first]){if(p.second != to){s.push(P(to, p.first));}}}}}void BuildPath(){stack<P> s;centroids.emplace_back(-1, -1, 0, 0);s.push(P(0, -1));pathorder[0] = 0;while(!s.empty()) {P p = s.top();s.pop();pathid[p.first] = centroids[pathorder[p.first]].sz;for(int to : G[p.first]){if(p.second == to) continue;if(to == nxpath[p.first]){ // Centroid-Pathについてpathorder[to] = pathorder[p.first];}else{ // Centroid-Pathでないものについてpathorder[to] = (int)centroids.size();centroids.emplace_back(pathorder[p.first], pathid[p.first], centroids[pathorder[p.first]].depth + 1,0);}s.emplace(to, p.first);}centroids[pathorder[p.first]].sz++;}}void Build_index(){int ptr = 0;for(auto& centroid : centroids){index.push_back(ptr);ptr += centroid.sz;}}void add_edge(int x, int y){G[x].push_back(y), G[y].push_back(x);}void Build(){Buildstsize(); BuildPath(), Build_index();}//idxが何番目のパスの何番目かinline P info(int idx){return P(pathorder[idx], pathid[idx]);}//元の頂点のインデックスの配列上でのidを返すinline int get(int a){P p = info(a);return (index[p.first] + p.second);}inline Centroid &operator[](int k){return (centroids[k]);}inline void query(int a, int b, const function< void(int, int) > &func){int pathidA, pathdepthA, pathidB, pathdepthB;tie(pathidA, pathdepthA) = info(a);tie(pathidB, pathdepthB) = info(b);while(pathidA != pathidB) {if(centroids[pathidA].depth > centroids[pathidB].depth) {func(index[pathidA], index[pathidA] + pathdepthA + 1);tie(pathidA, pathdepthA) = centroids[pathidA].Up();}else{func(index[pathidB], index[pathidB] + pathdepthB + 1);tie(pathidB, pathdepthB) = centroids[pathidB].Up();}}if(pathdepthA > pathdepthB) swap(pathdepthA, pathdepthB);func(index[pathidA] + pathdepthA, index[pathidA] + pathdepthB + 1);}HLdecomposition(int SZ){G.resize(SZ);stsize.assign(SZ, -1);nxpath.resize(SZ);pathorder.resize(SZ);pathid.resize(SZ);}};ll add(ll x,ll y){return (x + y)%MOD;}ll sub(ll x,ll y){return (x+MOD-y)%MOD;}ll mul(ll x,ll y){return x*y%MOD;}template<typename V> class segtree {private:int n,sz;vector<V> node, lazy, sm;public:segtree(vector<V>& u,vector<V>& v) {sz = (int)v.size();n = 1;while(n < sz){n *= 2;}node.resize(2*n-1);lazy.resize(2*n-1, 0);sm.resize(n+1,0);sm[0] = 0;rep(i,sz){sm[i+1] = add(sm[i],u[i]);}rep(i,sz){node[i+n-1] = v[i];}for(int i=n-2; i>=0; i--){node[i] = add(node[i*2+1],node[i*2+2]);}}int sum(int l,int r){return sub(sm[r],sm[l]);}void eval(int k, int l, int r) {if(lazy[k] != 0) {node[k] = add(node[k],mul(sum(l,r),lazy[k])); //kを根とするsubtreeについての情報を更新if(r - l > 1) {lazy[2*k+1] = add(lazy[2*k+1],lazy[k]);lazy[2*k+2] = add(lazy[2*k+2],lazy[k]);}lazy[k] = 0;}}void range(int a, int b, V x, int k=0, int l=0, int r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a){return;}if(a <= l && r <= b) {lazy[k] = add(lazy[k],x);eval(k, l, r);}else{range(a, b, x, 2*k+1, l, (l+r)/2);range(a, b, x, 2*k+2, (l+r)/2, r);node[k] = add(node[2*k+1],node[2*k+2]);}}V query(int a, int b, int k=0, int l=0, int r=-1) {if(r < 0) r = n;eval(k, l, r);if(b <= l || r <= a){return 0;}if(a <= l && r <= b){return node[k];}V vl = query(a, b, 2*k+1, l, (l+r)/2);V vr = query(a, b, 2*k+2, (l+r)/2, r);return add(vl,vr);}void print(){rep(i,sz){cout << query(i,i+1) << " ";}cout << endl;}};int main(){int n;scanf("%d",&n);vi s(n),c(n);rep(i,n){scanf("%d",&s[i]);}rep(i,n){scanf("%d",&c[i]);}HLdecomposition hl(n);rep(i,n-1){int a,b;scanf("%d%d",&a,&b);hl.add_edge(a-1,b-1);}hl.Build();int Q;scanf("%d",&Q);vi d(n),e(n);rep(i,n){d[hl.get(i)] = c[i];e[hl.get(i)] = s[i];}segtree<int> seg(d,e);rep(i,Q){int p,q,r;scanf("%d%d%d",&p,&q,&r);--q,--r;if(p == 0){int s;scanf("%d",&s);hl.query(q, r, [&](int l, int r){ seg.range(l, r, s); });}else{int ans = 0;hl.query(q, r, [&](int l, int r){ ans = add(ans,seg.query(l, r)); });printf("%d\n", ans);}}}