結果

問題 No.235 めぐるはめぐる (5)
ユーザー Eki1009Eki1009
提出日時 2022-01-28 14:54:10
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,011 bytes
コンパイル時間 4,585 ms
コンパイル使用メモリ 266,932 KB
実行使用メモリ 29,004 KB
最終ジャッジ日時 2023-08-28 12:12:47
合計ジャッジ時間 10,777 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:32:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type]
   32 | main(){
      | ^~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using mint=modint998244353;
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