結果

問題 No.235 めぐるはめぐる (5)
ユーザー Eki1009Eki1009
提出日時 2022-01-28 14:56:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,393 ms / 10,000 ms
コード長 2,012 bytes
コンパイル時間 4,723 ms
コンパイル使用メモリ 260,880 KB
最終ジャッジ日時 2025-01-27 15:50:51
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:32:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
   32 | main(){
      | ^~~~
main.cpp: In function ‘int main()’:
main.cpp:34:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |   scanf("%d",&n);
      |   ~~~~~^~~~~~~~~
main.cpp:35:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |   for(int i=0;i<n;i++)scanf("%d",&S[i]);
      |                       ~~~~~^~~~~~~~~~~~
main.cpp:36:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   36 |   for(int i=0;i<n;i++)scanf("%d",&C[i]);
      |                       ~~~~~^~~~~~~~~~~~
main.cpp:39:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   39 |     scanf("%d%d",&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~
main.cpp:49:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |   scanf("%d",&q);
      |   ~~~~~^~~~~~~~~
main.cpp:52:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   52 |     scanf("%d",&t);
      |     ~~~~~^~~~~~~~~
main.cpp:55:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   55 |       scanf("%d%d%d",&x,&y,&z);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:69:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   69 |       scanf("%d%d",&x,&y);
      |       ~~~~~^~~~~~~~~~~~~~

ソースコード

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