結果

問題 No.900 aδδitivee
ユーザー latte0119
提出日時 2019-10-05 01:11:10
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 3,111 bytes
コンパイル時間 1,819 ms
コンパイル使用メモリ 173,300 KB
実行使用メモリ 36,260 KB
最終ジャッジ日時 2024-10-04 03:09:07
合計ジャッジ時間 8,142 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:136:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  136 |         int N;scanf("%lld",&N);
      |               ~~~~~^~~~~~~~~~~
main.cpp:140:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  140 |                 scanf("%lld%lld%lld",&a,&b,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:148:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  148 |         int Q;scanf("%lld",&Q);
      |               ~~~~~^~~~~~~~~~~
main.cpp:150:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  150 |                 int t;scanf("%lld",&t);
      |                       ~~~~~^~~~~~~~~~~
main.cpp:153:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  153 |                         scanf("%lld%lld",&a,&x);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:158:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  158 |                         int b;scanf("%lld",&b);
      |                               ~~~~~^~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<class W,int lg=1>
struct WeightedTree{
    struct Edge{
        int to;
        W cost;
        Edge(int to,W cost):to(to),cost(cost){}
    };
    int V;
    vector<vector<Edge>>G;
    vector<vector<int>>par;
    vector<int>dep,sz,head;
    vector<int>tin,tout;
    vector<W>dist;
    WeightedTree(int V):V(V),G(V),par(lg,vector<int>(V)),sz(V),dep(V),head(V),dist(V),tin(V),tout(V){}
    void addEdge(int a,int b,W c=W(1)){
        G[a].push_back(Edge(b,c));
        G[b].push_back(Edge(a,c));
    }
    void dfs(int v,int p,int d,W c){
        par[0][v]=p;
        dep[v]=d;
        sz[v]=1;
        dist[v]=c;
        for(auto &e:G[v]){
            if(e.to==p)continue;
            dfs(e.to,v,d+1,c+e.cost);
            sz[v]+=sz[e.to];
            if(G[v][0].to==p||sz[e.to]>sz[G[v][0].to])swap(G[v][0],e);
        }
    }
    void dfs_hld(int v,int &tt){
        tin[v]=tt++;
        for(auto &e:G[v]){
            if(e.to==par[0][v])continue;
            head[e.to]=(e.to==G[v][0].to)?head[v]:e.to;
            dfs_hld(e.to,tt);
        }
        tout[v]=tt;
    }
    void init(){
        dfs(0,-1,0,W(0));
        int tt=0;
        dfs_hld(0,tt);
        for(int i=0;i+1<lg;i++){
            for(int j=0;j<V;j++){
                if(par[i][j]==-1)par[i+1][j]=-1;
                else par[i+1][j]=par[i][par[i][j]];
            }
        }
    }
    // 1<<lg >=N-1!!!!!
    int getLCA(int u,int v){
        
        if(dep[u]<dep[v])swap(u,v);
        rep(i,lg)if((dep[u]-dep[v])>>i&1)u=par[i][u];
        if(u==v)return u;
        for(int i=lg-1;i>=0;i--)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
        return par[0][v];
    }
    int getLength(int a,int b=0){
        int l=getLCA(a,b);
        return dep[a]+dep[b]-2*dep[l];
    }
    W getDistance(int a,int b=0){
        int l=getLCA(a,b);
        return dist[a]+dist[b]-2*dist[l];
    }
    int getPar(int v,int k=0){
        return par[k][v];
    }
    int getDepth(int v){
        return dep[v];
    }
    int getIn(int v){
        return tin[v];
    }
    int getOut(int v){
        return tout[v];
    }
};
/*
0-indexed
add(k,x): a[k]+=x
sum(k): sum(a[0,k])
space:O(N)
time:O(logN) per query
*/
struct BinaryIndexedTree{
    int n;
    vector<int>dat;
    BinaryIndexedTree(int n=0):n(n){
        dat.resize(n+1);
    }
    void add(int k,int x){
        for(k++;k<=n;k+=k&-k)dat[k]+=x;
    }
    int sum(int k){
        int ret=0;
        for(k++;k;k-=k&-k)ret+=dat[k];
        return ret;
    }
};
signed main(){
    int N;scanf("%lld",&N);
    WeightedTree<int,20>T(N);
    rep(i,N-1){
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        T.addEdge(a,b,c);
    }
    T.init();
    BinaryIndexedTree bit0(111111),bit1(111111);
    int Q;scanf("%lld",&Q);
    while(Q--){
        int t;scanf("%lld",&t);
        if(t==1){
            int a,x;
            scanf("%lld%lld",&a,&x);
            bit1.add(T.getIn(a),x);bit1.add(T.getOut(a),-x);
            bit0.add(T.getIn(a),-T.getDepth(a)*x);bit0.add(T.getOut(a),T.getDepth(a)*x);
        }
        else{
            int b;scanf("%lld",&b);
            int ans=T.getDistance(b);
            ans+=bit0.sum(T.getIn(b));
            ans+=bit1.sum(T.getIn(b))*T.getDepth(b);
            printf("%lld\n",ans);
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0