結果

問題 No.235 めぐるはめぐる (5)
ユーザー Eki1009Eki1009
提出日時 2022-01-28 14:56:25
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,229 ms / 10,000 ms
コード長 2,012 bytes
コンパイル時間 4,667 ms
コンパイル使用メモリ 271,760 KB
実行使用メモリ 28,160 KB
最終ジャッジ日時 2024-06-09 07:40:51
合計ジャッジ時間 10,021 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,229 ms
27,264 KB
testcase_01 AC 791 ms
28,160 KB
testcase_02 AC 1,124 ms
27,648 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | main(){
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=modint1000000007;
vector<int>G[2<<17];
int num,in[2<<17],nxt[2<<17],par[2<<17],sz[2<<17],S[2<<17],C[2<<17];
void dfs_sz(int u){
  sz[u]=1;
  if(G[u][0]==par[u])swap(G[u][0],G[u].back());
  for(int&v:G[u]){
    if(v==par[u])continue;
    par[v]=u;
    dfs_sz(v);
    sz[u]+=sz[v];
    if(sz[v]>sz[G[u][0]])swap(v,G[u][0]);
  }
}
void dfs_hld(int u){
  in[u]=num++;
  for(int v:G[u]){
    if(v==par[u])continue;
    nxt[v]=v==G[u][0]?nxt[u]:v;
    dfs_hld(v);
  }
}
pair<mint,mint>op(pair<mint,mint>a,pair<mint,mint>b){return{a.first+b.first,a.second+b.second};}
pair<mint,mint>e(){return{0,0};}
pair<mint,mint>mp(mint f,pair<mint,mint>x){return{x.first,x.second+x.first*f};}
mint cmp(mint f,mint g){return f+g;}
mint id(){return 0;}
main(){
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++)scanf("%d",&S[i]);
  for(int i=0;i<n;i++)scanf("%d",&C[i]);
  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);
  }
  dfs_sz(0),dfs_hld(0);
  vector<pair<mint,mint>>V(n);
  for(int i=0;i<n;i++)V[in[i]]={C[i],S[i]};
  lazy_segtree<pair<mint,mint>,op,e,mint,mp,cmp,id>seg(V);
  int q;
  scanf("%d",&q);
  for(int i=0;i<q;i++){
    int t;
    scanf("%d",&t);
    if(t==0){
      int x,y,z;
      scanf("%d%d%d",&x,&y,&z);
      x--,y--;
      while(1){
        if(in[x]>in[y])swap(x,y);
        if(nxt[x]==nxt[y]){
          seg.apply(in[x],in[y]+1,z);
          break;
        }else{
          seg.apply(in[nxt[y]],in[y]+1,z);
          y=par[nxt[y]];
        }
      }
    }else{
      int x,y;
      scanf("%d%d",&x,&y);
      x--,y--;
      mint ans=0;
      while(1){
        if(in[x]>in[y])swap(x,y);
        if(nxt[x]==nxt[y]){
          ans+=seg.prod(in[x],in[y]+1).second;
          break;
        }else{
          ans+=seg.prod(in[nxt[y]],in[y]+1).second;
          y=par[nxt[y]];
        }
      }
      printf("%d\n",ans.val());
    }
  }
}
0