結果

問題 No.235 めぐるはめぐる (5)
コンテスト
ユーザー Kmcode1
提出日時 2015-06-26 23:41:13
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 5,264 bytes
コンパイル時間 1,277 ms
コンパイル使用メモリ 118,052 KB
実行使用メモリ 102,112 KB
最終ジャッジ日時 2024-07-07 18:35:59
合計ジャッジ時間 5,474 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:219:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  219 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
main.cpp:221:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  221 |                 scanf("%lld", &s[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:224:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  224 |                 scanf("%lld", &c[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:228:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  228 |                 scanf("%d%d", &a, &b);
      |                 ~~~~~^~~~~~~~~~~~~~~~
main.cpp:242:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  242 |         scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
main.cpp:245:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  245 |                 scanf("%d", &ty);
      |                 ~~~~~^~~~~~~~~~~
main.cpp:249:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  249 |                         scanf("%d%d%lld", &a, &b, &z);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:259:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  259 |                         scanf("%d%d", &a, &b);
      |                         ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
using namespace std;
#define MOD 1000000007
#define MAX 200002
class L{
public:
	struct st{
		long long int lazy = 0;  //for ans
		long long int sum = 0;  //sum of c
		long long int ans = 0;  //ans sum
		int l = 0;
		int r = 0;
		long long int area = 0;
	};
	vector<st> seg;
	vector<long long int> C;
	vector<long long int> S;
	int N = 0;
	void update(int b){
		seg[b].ans += seg[b].sum*seg[b].lazy;
		seg[b].ans %= MOD;
		if (seg[b].l + 1 == seg[b].r){
			seg[b].lazy = 0;
			return;
		}
		seg[b * 2 + 1].lazy += seg[b].lazy;
		seg[b * 2 + 2].lazy += seg[b].lazy;
		seg[b * 2 + 1].lazy %= MOD;
		seg[b * 2 + 2].lazy %= MOD;
	}
	inline void init(int b, int l, int r){
		seg[b].l = l;
		seg[b].r = r;
		seg[b].area = r - l;
		if (l + 1 == r){
			seg[b].sum = C[l];
			seg[b].ans = S[l];
			return;
		}
		init(b * 2 + 1, l, (l + r) >> 1);
		init(b * 2 + 2, (l + r) >> 1, r);
		seg[b].sum = seg[b * 2 + 1].sum + seg[b * 2 + 2].sum;
		seg[b].sum %= MOD;
		seg[b].ans = seg[b * 2 + 1].ans + seg[b * 2 + 2].ans;
		seg[b].ans %= MOD;
	}
	inline void add1(int b, int l, int r, int ll, int rr, int x){
		update(b);
		if (ll <= l&&r <= rr){
			seg[b].lazy = x;
			update(b);
			return;
		}
		if (r <= ll || rr <= l){
			return;
		}
		add1(b * 2 + 1, l, (l + r) >> 1, ll, rr, x);
		add1(b * 2 + 2, (l + r) >> 1, r, ll, rr, x);
		seg[b].ans= seg[b * 2 + 1].ans + seg[b * 2 + 2].ans;
		seg[b].ans %= MOD;
	}
	inline long long int q(int b, int l, int r, int ll, int rr){
		update(b);
		if (r <= ll || rr <= l){
			return 0;
		}
		if (ll <= l&&r <= rr){
			return seg[b].ans;
		}
		long long int R = q(b * 2 + 1, l, (l + r) >> 1, ll, rr);
		long long int RR = q(b * 2 + 2, (l + r) >> 1, r, ll, rr);
		R += RR;
		R %= MOD;
		return R;
	}
	void set(int n){
		N = n;
		seg.assign(n * 4,st());
		init(0, 0, N);
	}
	long long int sum(int l, int r){
		return q(0, 0, N, l, r);
	}
	void add(int l, int r, long long int x){
		add1(0, 0, N, l, r, x);
	}
};
int countt[MAX];
int belong[MAX];
int att[MAX];
#define MAX_LOG 21
vector<L> HL;
int lcc[MAX_LOG][MAX];
int dep[MAX];
bool use[MAX];
vector<int> v[MAX];
vector<int> g[MAX];
int n;
long long int s[MAX];
long long int c[MAX];
int pr[MAX];
inline void dfs(int b,int pre=-1,int h=0){
	dep[b] = h;
	lcc[0][b] = pre;
	use[b] = true;
	countt[b] = 1;
	for (int i = 0; i < v[b].size(); i++){
		if (use[v[b][i]] == false){
			dfs(v[b][i],b,h+1);
			g[b].push_back(v[b][i]);
			countt[b] += countt[v[b][i]];
		}
	}
}
void init(){
	for (int i = 0; i + 1 < MAX_LOG; i++){
		for (int j = 0; j < n; j++){
			if (lcc[i][j] == -1){
				lcc[i + 1][j] = -1;
				continue;
			}
			lcc[i + 1][j] = lcc[i][lcc[i][j]];
		}
	}
}
int lca(int a, int b){
	if (dep[a] < dep[b]){
		swap(a, b);
	}
	for (int i = 0; i < MAX_LOG; i++){
		if (((dep[a] - dep[b]) >> i) & 1){
			a = lcc[i][a];
		}
	}
	if (a == b){
		return a;
	}
	for (int i = MAX_LOG - 1; i >= 0; i--){
		if (lcc[i][a] != lcc[i][b]){
			a = lcc[i][a];
			b = lcc[i][b];
		}
	}
	return lcc[0][a];
}
inline void dfs2(int a, int b, int cc){
	belong[a] = b;
	att[a] = cc;
	HL[b].S.push_back(s[a]);
	HL[b].C.push_back(c[a]);
	if (v[a].size() == 0){
		HL[b].set(cc + 1);
		return;
	}
	int maxt = 0;
	int ind = 0;
	for (int i = 0; i < v[a].size(); i++){
		if (maxt <= countt[v[a][i]]){
			maxt = countt[v[a][i]];
			ind = i;
		}
	}
	for (int i = 0; i < v[a].size(); i++){
		if (i == ind){
			dfs2(v[a][i], b, cc + 1);
		}
		else{
			pr[HL.size()] = a;
			HL.push_back(L());
			dfs2(v[a][i], HL.size() - 1, 0);
		}
	}
}
void paint(int a, int b,long long int z){
	long long int r = 0;
	while (belong[b] != belong[a]){
		HL[belong[b]].add(0, att[b] + 1,z);
		b = pr[belong[b]];
	}
	HL[belong[b]].add(att[a], att[b] + 1,z);
}
long long int sum_up(int a, int b){
	long long int r = 0;
	while (belong[b] != belong[a]){
		r += HL[belong[b]].sum(0, att[b] + 1);
		r %= MOD;
		b = pr[belong[b]];
	}
	r += HL[belong[b]].sum(att[a], att[b] + 1);
	r %= MOD;
	return r;
}
int main(){
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%lld", &s[i]);
	}
	for (int i = 0; i < n; i++){
		scanf("%lld", &c[i]);
	}
	for (int i = 1; i < n; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(0);
	init();
	HL.push_back(L());
	for (int i = 0; i < n; i++){
		swap(v[i], g[i]);
	}
	dfs2(0, 0, 0);
	int q;
	scanf("%d", &q);
	while (q--){
		int ty;
		scanf("%d", &ty);
		if (ty == 0){
			int a, b;
			long long int z;
			scanf("%d%d%lld", &a, &b, &z);
			a--;
			b--;
			int lc = lca(a, b);
			paint(lc, b, z);
			paint(lc, a, z);
			paint(lc, lc, -z);
		}
		else{
			int a, b;
			scanf("%d%d", &a, &b);
			a--;
			b--;
			int lc = lca(a, b);
			long long int ans = sum_up(lc, a);
			ans += sum_up(lc, b);
			ans %= MOD;
			ans += MOD - sum_up(lc, lc);
			ans %= MOD;
			printf("%lld\n", ans);
		}
	}
	return 0;
}
0