結果

問題 No.900 aδδitivee
ユーザー latte0119latte0119
提出日時 2019-10-05 01:11:10
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 163 ms
32,952 KB
testcase_08 AC 147 ms
32,948 KB
testcase_09 AC 167 ms
32,820 KB
testcase_10 AC 159 ms
32,816 KB
testcase_11 AC 154 ms
32,944 KB
testcase_12 AC 159 ms
32,948 KB
testcase_13 AC 158 ms
33,076 KB
testcase_14 AC 158 ms
32,824 KB
testcase_15 AC 151 ms
33,060 KB
testcase_16 AC 157 ms
32,952 KB
testcase_17 AC 154 ms
32,768 KB
testcase_18 AC 155 ms
32,948 KB
testcase_19 AC 154 ms
33,076 KB
testcase_20 AC 160 ms
32,948 KB
testcase_21 AC 168 ms
32,948 KB
testcase_22 AC 146 ms
36,024 KB
testcase_23 AC 155 ms
36,260 KB
testcase_24 AC 150 ms
36,020 KB
testcase_25 AC 148 ms
36,020 KB
testcase_26 AC 141 ms
36,148 KB
testcase_27 AC 148 ms
36,024 KB
testcase_28 AC 144 ms
36,020 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0