首页

100 + 100 + 0
中间好像摆了不少时间，导致没有深入思考 T3
T1 做到快下考，其实根本不难写，但怕翻车写了比正解还长的暴力并拍了很久

# common

一棵以 rtrt 为根的树，点带权，定义 sumisum_i 表示点 ii 为根的子树 内权值和，两种操作：1. 单点修改 2. 求 ∑i=lrsumi\sum\limits_{i=l}^r sum_i

n,m≤1×105n,m\le 1\times 10^5

# Sol:

没有看错，是子树内权值和

首先能得出一个十分 naivenaive 的暴力，使用 BITBIT 单点修改，再暴力的处理询问，这样修改复杂度 O(log⁡n)\mathrm O(\log n) ，询问复杂度 O(n×log⁡n)\mathrm O(n \times \log n)

如果你看到 7070 分暴力忍不出了开始 rushrush ，没准你就走上了错误的道路

然后我们发现修改快的像正解，而询问有亿点点慢，于是我们考虑一个经典套路 – 根号平衡

把原点序列分个块，再预处理出每个点在每个块的影响力，就可以 O(log⁡nn\mathrm O(\log n \sqrt n 查询， O(nlog⁡n)\mathrm O(\sqrt n \log n) 修改乐。

#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/* ==============================
 *  Author : Odalys 
 *
 *  Mail : minyuenu@gmail.com
 * =============================== */
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define int unsigned int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int, int> 
#define vi vector<int> 
#define wife puts("MckennaGrace")
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 1e5 + 10;
struct edge {
	int to, nxt;  
} e[N << 1];
int head[N], cnt, val[N];
inline void add (int u, int v) {
	e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;
}

int n, m, rt;
int dfn[N], dfntot, low[N];
struct BIT {
	int sum[N];
	inline void upd (int x, int v) { 
		for (int i = x; i <= n; i += (i & (-i))) 
			sum[i] += v; 
		}
	inline int ask (int x) { 
		int Ans = 0; 
		for (int i = x; i; i -= (i & (-i))) Ans += sum[i]; 
		return Ans; 
	}
} tr; 
int Sum[N];
void dfs (int u, int fa) {
	dfn[u] = ++dfntot;
	Sum[u] = val[u]; 
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == fa) continue;
		dfs(v, u); 
		Sum[u] += Sum[v];
	}
	low[u] = dfntot;
} 
int bel[N], siz, blo, Ans[N];
int To[N][318];
void dfs1 (int u, int fa) {
	To[u][bel[u] - 1]++;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == fa) continue;
		For (j, 0, blo - 1) 
			To[v][j] += To[u][j];
		dfs1(v, u); 
	}
}

inline void work (int u, int v) {
	For (i, 0, blo - 1) {
		int x = To[u][i];
		Ans[i + 1] += x * (v - val[u]);
	}
	tr.upd(dfn[u], v - val[u]);
	val[u] = v;
}

inline int sol (int l, int r) {
	int ret = 0;
	//if (bel[l] < bel[r]) return 0;
	if (bel[l] == bel[r]) {
		For (i, l, r) 
			ret += tr.ask(low[i]) - tr.ask(dfn[i] - 1);
		return ret;	
	}
	For (i, bel[l] + 1, bel[r] - 1)
		ret += Ans[i];
	For (i, l, min(n, bel[l] * siz))
		ret += tr.ask(low[i]) - tr.ask(dfn[i] - 1);
	For (i, (bel[r] - 1) * siz + 1, r)
		ret += tr.ask(low[i]) - tr.ask(dfn[i] - 1); 

	return ret;
}

signed main() {
	read(n), read(m);
	For (i, 1, n) read(val[i]);
	For (i, 1, n) {
		int u, v; read(u); read(v);
		if (!u) rt = v;
		else add(u, v), add(v, u); 
	}
	dfs(rt, 0); 
	For (i, 1, n) 
		tr.upd(dfn[i], val[i]); 
	siz = sqrt (n), blo = n / siz;
	for (int i = 1; i <= blo; ++i) 
		For (j, (i - 1) * siz + 1, i * siz) 
			bel[j] = i, Ans[i] += Sum[j];
	if (blo * siz < n){
		For (i, blo * siz + 1, n) bel[i] = blo + 1;
		blo++;
	}
	dfs1(rt, 0);
	//For (i, 1, n) 
	//	Debug(dfn[i]), Debug(low[i]); 
	//For (i, 1, n)
	//	cout << bel[i] << " " ;
	//puts("");
	while (m--) {
		int opt, u, v; read(opt); read(u); read(v);
		if (opt == 1) 
			work (u, v);		
		else 
			printf ("%llu\n", sol(u, v));
	}
	return 0;
	
}

# art

kn,mk_{n,m} ，求生成树个数

n,m≤1×1018n,m\le 1\times 10^{18}

# Sol:

这个 n,mn,m 范围一看就有结论啦

使用 matrixtreematrix\ tree 玩一玩矩阵可得到结论

Ans=nm−1×mn−1Ans = n^{m-1} \times m^{n-1}

注意到 n,mn,m 一乘就爆 ll 于是要使用龟速乘

# hands

从 (0,0)(0,0) 出发，每次可前往 (u+Ax,v+Ay)/(u+Bx,v+By)(u+Ax, v+Ay) / (u+Bx, v+By) ，问到 (n,m)(n,m) 的方案数

n,m≤500,∣Ax∣,∣Ay∣,∣Bx∣,∣By∣≤500n,m\le 500, |Ax|,|Ay|,|Bx|,|By|\le 500

# Sol:

乍一看像是 iodwadiodwad 出过的题
实际上也是的
虽然这玩意可以走负的，但把这两种走法看做两个向量，题目保证这两个向量不平行，也就意味着这两个向量可以张成所有点，于是转换一下坐标就是那道题了。