ytczy666

7111

# Solution

## 暴力

$\;$

$\;$

## 状压dp

$\;$

$O(2^n \times n^2 \times m^2)$的

$\sum max(0,a_j - a_i) \times (n- p_i +1)$
$p_i$代表$i$队伍是第几个选的。

# Code

#include <bits/stdc++.h>

const int N = 13, M = 505;

#define ll long long
int n, m, a[N];

ll f[1 << N][N + 1][M];
int main() {
scanf("%d%d", &n, &m);
int t = n;
for (int i = 0; i < n; i ++) {
scanf("%d", &a[i]);
if (a[i] > a[t]) t = i;
}
for (int i = 0; i < n; i ++) {
int add = n * (a[t] - a[i] + (i > t));
if (add <= m) f[1 << i][i][add] = 1;
}
for (int i = 1; i < (1 << n); i ++) {
int cnt = 0;
for (int j = 0; j < n; j ++) if (i >> j & 1) cnt ++;
for (int j = 0; j < n; j ++) if (i >> j & 1)
for (int k = 0; k <= m; k ++)
for (int l = 0; l < n; l ++) if ((i | (1 << l)) != i) {
int add = (n - cnt) * std::max(0, a[j] - a[l] + (l > j));
if (k + add <= m) f[i | (1 << l)][l][k + add] += f[i][j][k];
}
}
ll ans = 0;
for (int i = 0; i < n; i ++)
for (int j = 0; j <= m; j ++)
ans += f[(1 << n) - 1][i][j];
printf("%lld", ans);
return 0;
}


### 博客使用更佳：

https://www.cnblogs.com/czyty114/p/14742702.html

# 题意

$\;$

$n\leq 10^9, k\leq 200$
$\;$
input
3 2
output
3 3
$\;$

$\;$

# Solution

$\;$

$\;$

！第一类斯特林数（当场自闭
$\;$

## 第一类斯特林数

$\;$
$S1(n,m)$代表一个长度为$n$的排列被划分成$m$个轨道的方案数

$S1(n,m)=S1(n-1,m-1)+(n-1)S1(n-1,m)$

$\;$

## 处理n很大的情况

$\;$

$$S1(n,m)=(-1)^{n-m}\sum_{i=0}^{n-m} (-1)^i \times C(n-1+i,n-m+i) \times C(2n-m,n-m-i) \times S(n-m+i,i)$$
$\;$

$\;$

# Code

#include <bits/stdc++.h>

const int N = 410, mod = 1000000007;

int n, k, fac[N], inv[N], S[N][N], dp[N];

int C(int n, int m) {
int ans = 1;
for (int i = n; i >= n - m + 1; i --) ans = 1ll * ans * i % mod;
return 1ll * ans * inv[m] % mod;
}

int power(int a, int b) {
int ans = 1;
while(b) {
if (b & 1) ans = 1ll * ans * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return ans;
}
int main() {
scanf("%d%d", &n, &k);
fac[0] = inv[0] = 1;
for (int i = 1; i <= 400; i ++) {
fac[i] = 1ll * fac[i - 1] * i % mod;
inv[i] = power(fac[i], mod - 2);
}
S[0][0] = 1;
for (int i = 1; i <= 400; i ++)
for (int j = 1; j <= i; j ++)
S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j] % mod) % mod;
for (int i = 0; i <= k; i ++) // 求s(n,n-i)
for (int j = 0; j <= i; j ++) {
if (j & 1)
dp[i] = (dp[i] - 1ll * C(n - 1 + j, i + j) * C(n + i, i - j) % mod * S[i + j][j] % mod + mod) % mod;
else
dp[i] = (dp[i] + 1ll * C(n - 1 + j, i + j) * C(n + i, i - j) % mod * S[i + j][j] % mod) % mod;
}
for (int i = 1; i <= k; i ++) {
int ans = 0;
for (int j = 0; j <= i; j += 2)
ans = (ans + dp[i - j]) % mod;
if (i % 2 == 0) printf("%d ", ans);
else printf("%d ", mod - ans);
}
return 0;
}


ytczy666
22天前

# A

$\;$
$n$个人，$m$道题，每道题有两个选项。现在给出了这$n$个人的作答，用$n$个长度为$m$的01串来表示。

$n\leq 10^5,m\leq 20$
$\;$

$\;$

# B

$\;$

$n \leq 500$
$\;$

$O(n^2)$简单判断一下是否是无解情况就行了
$\;$

# C

$\;$

$n\leq 10^5$
$\;$

$\;$

# D

$\;$

$n\leq 5000$
$\;$

$\;$

$\;$

ytczy666
22天前

# B

$\;$

## 题意

$\;$

$n\leq 10^5,a_i\leq 10^9$
input
2
1 2
output
4
$\;$

## Solution

$\;$

$$Ans = \prod_{i=1}^n (a_i-a_{i-1}+1)$$
$\;$

# C

## 题意

$\;$

$n\leq 4 \times 10^5$
input
RRBB
output
W
$\;$

## Solution

$\;$

$$-(a+b)\;(mod \;3)$$
$\;$

$$(-1)^{n-1} \times \sum_{i=0}^{n-1} C_{n-1}^i s_i\; (mod \; 3)$$
$\;$

Lucas: 若$p$是质数，$C(n,m) = C(n/p,m/p) \times C(n\%p,m\%p)$

$\;$

# E

$\;$

## 题意

$\;$

1.恰好有$n$个1和$n$个-1
2.恰好有$k$个$(l,r)$，满足$a_l+a_{l+1}+\cdots +a_r = 0$
$n\leq 30, k\leq n^2$
input
3 7
output
6
$\;$

## Solution

$\;$

$dp_{i,j,k}$表示当前填了$i$个数，且有$j$个$(l,r)$满足条件，目前填的数中$hole$的数量为$k$的方案数。
$hole$表示序列中相邻两个元素值相同之间的空隙。

ytczy666
1个月前

ytczy666
1个月前

# A

$\;$
$n$个人，$m$道题，每道题有两个选项。现在给出了这$n$个人的作答，用$n$个长度为$m$的01串来表示。

$n\leq 10^5,m\leq 20$
$\;$

$\;$

# B

$\;$

$n \leq 500$
$\;$

$O(n^2)$简单判断一下是否是无解情况就行了
$\;$

# C

$\;$

$n\leq 10^5$
$\;$

$\;$

# D

$\;$

$n\leq 5000$
$\;$

$\;$

$\;$

ytczy666
2个月前

### 博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$

$\;$

## 引入

$\;$

$\;$

# 普通莫队

$\;$

## 核心

$\;$

$n,m\leq 10^5$

$\;$

## 时间复杂度

$\;$

(注意：这里我们假设m与n同阶)
$\;$

$\;$

$\;$

$\;$

$\;$

## Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
int pos, l, r;
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块
return a.r < b.r; // 右端点所属位置
}
int main() {
scanf("%d", &n);
sq = (int)sqrt(n);
for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号
for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
std::sort(b + 1, b + n + 1);
nn = std::unique(b + 1, b + n + 1) - b - 1;
for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
//----------------- 上面是离散化部分，不多赘述
scanf("%d", &m);
std::sort(ask + 1, ask + m + 1, cmp);
int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针
for(int i=1;i<=m;i++) {
int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点
while(x < l) { // 左端点向右移，区间缩小
cnt[a[x]] --; if(!cnt[a[x]]) -- res;
x ++;
}

while(x > l) { // 左端点向左移，区间变大
cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
x --;
}

while(y < r) { // 右端点向右移，区间变大
cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
y ++;
}

while(y > r) { // 右端点向左移，区间缩小
cnt[a[y]] --; if(!cnt[a[y]]) -- res;
y --;
}

ans[ask[i].pos] = res; // 注意：i是排序后区间的编号，但并不是输入时询问的编号
}
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
return 0;
}


# 带修莫队

$\;$

$\;$

## 时间复杂度

$\;$

$\;$

$\;$

$\;$

## Code

$\;$

https://www.luogu.com.cn/problem/P1903

#include <bits/stdc++.h>

#define fi first
#define se second
const int N = 143333;
int n, m, k, a[N], cnt[N * 10], ans[N], id[N], sq, T, b[N], res, x, y;
std::pair<int,int> cur[N], fur[N];
struct node {
int l, r, t, pos;

bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
if(id[a.r] != id[b.r]) return id[a.r] < id[b.r];
return a.t < b.t;
}

bool g(int d) {
return (x <= d && d <= y);
}
void gg(int x, int y) {
cnt[x] --; cnt[y] ++;
if(!cnt[x]) -- res; if(cnt[y] == 1) ++ res;
}
int main() {
scanf("%d%d", &n, &m);
sq = pow(n, 3.0 / 4);
for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq);
for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
for(int i=1;i<=m;i++) {
char op[5]; int l, r;
scanf("%s", op);
scanf("%d%d", &l, &r);
if(op[0] == 'Q') {
++ k; ask[k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
}
else {
cur[i].fi = l; cur[i].se = r;
fur[i].fi = l; fur[i].se = b[l]; b[l] = r;
}
}
std::sort(ask + 1, ask + k + 1, cmp);
int ti = 0;
for(int i=1;i<=k;i++) {
int t = ask[i].t, l = ask[i].l, r = ask[i].r;
while(ti < t) {
if(!cur[ti + 1].fi) {
ti ++; continue;
}
if(g(cur[ti + 1].fi)) gg(a[cur[ti + 1].fi], cur[ti + 1].se);
a[cur[ti + 1].fi] = cur[ti + 1].se;
ti ++;
}
while(ti > t) {
if(!fur[ti].fi) {
ti --; continue;
}
if(g(fur[ti].fi)) gg(a[fur[ti].fi], fur[ti].se);
a[fur[ti].fi] = fur[ti].se;
ti --;
}
while(x < l) {
cnt[a[x]] --; if(!cnt[a[x]]) -- res;
x ++;
}
while(x > l) {
cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
x --;
}
while(y < r) {
cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
y ++;
}
while(y > r) {
cnt[a[y]] --; if(!cnt[a[y]]) -- res;
y --;
}
}
for(int i=1;i<=k;i++) printf("%d\n", ans[i]);
return 0;
}


$\;$

# 树上莫队

$\;$

## 核心

$\;$

$\;$

## Code

$\;$

https://www.luogu.com.cn/problem/P4074
$\;$

#include <bits/stdc++.h>

const int N = 100010;

int n, m, k, q, top, val[N], w[N], tim[N], stk[N], idx, dfn[N], dep[N], S, lst[N], id[N], scc, c[N], bc[N];
int upd[N], pre[N], d[N], x, y, vis[N], f[N][20];
long long ans, res[N];
std::vector<int> G[N];
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return f * x;
}
int dfs(int u, int fa) {
int re = 0;
dfn[u] = ++idx;
f[u][0] = lst[u] = fa;
dep[u] = dep[fa] + 1;
for(int i=1;i<=19;i++) f[u][i] = f[f[u][i - 1]][i - 1];
for(int i=0;i<G[u].size();i++) {
int v = G[u][i];
if(v == fa) continue;
re += dfs(v, u);
if(re >= S) {
scc ++;
while(re)
id[stk[top --]] = scc, re --;
}
}
stk[++top] = u;
return re + 1;
}
struct node {
int l, r, pos, t;
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
if(id[a.r] != id[b.r]) {
if(id[a.l] & 1) return id[a.r] < id[b.r];
return id[a.r] > id[b.r];
}
return a.pos < b.pos;
}
int lca(int x, int y) {
if(x == y) return x;
if(dep[x] < dep[y]) std::swap(x, y);
int ch = dep[x] - dep[y], er = 0;
while(ch) {
if(ch & 1) x = f[x][er];
ch >>= 1; er ++;
}
if(x == y) return x;
for(int i=19;~i;i--) {
if(f[x][i] == f[y][i]) continue;
x = f[x][i]; y = f[y][i];
}
return f[x][0];
}
void change(int d, int v) {
if(vis[d]) {
ans = ans - 1ll * w[tim[c[d]] --] * val[c[d]];
ans = ans + 1ll * w[++ tim[v]] * val[v];
c[d] = v;
}
else c[d] = v;
}
void modify(int x) {
if(vis[x]) {
vis[x] = 0;
ans = ans - 1ll * val[c[x]] * w[tim[c[x]] --];
}
else {
vis[x] = 1;
ans = ans + 1ll * val[c[x]] * w[++tim[c[x]]];
}
}
void make_tag(int u, int v) {
while(u != v) {
if(dep[u] > dep[v]) modify(u), u = f[u][0];
else modify(v), v = f[v][0];
//printf("%d %d\n", u, v);
}
}
int main() {
S = pow(n, 0.666);
for(int i=1;i<=m;i++) val[i] = read();
for(int i=1;i<=n;i++) w[i] = read();
for(int i=1;i<n;i++) {
int u, v;
G[u].push_back(v); G[v].push_back(u);
}
dfs(1, 0);
scc ++;
for(int i=1;i<=n;i++) if(!id[i]) id[i] = scc;
for(int i=1;i<=n;i++) c[i] = read(), bc[i] = c[i];
for(int i=1;i<=q;i++) {
int op, l, r;
if(!op) {
upd[i] = r; d[i] = l; pre[i] = bc[l]; bc[l] = r;
}
else {
if(dfn[l] > dfn[r]) std::swap(l, r);
}
}
std::sort(ask + 1, ask + k + 1, cmp);
if(!upd[i]) continue;
change(d[i], upd[i]);
}
make_tag(x, y); modify(lca(x, y));
modify(lca(x, y));
for(int i=2;i<=k;i++) {
int l = ask[i].l, r = ask[i].r;
// time
int t = ask[i].t, p = ask[i - 1].t;
while(p < t) {
p ++;
if(upd[p]) change(d[p], upd[p]);
}
while(p > t) {
if(upd[p]) change(d[p], pre[p]);
p --;
}
make_tag(x, l);
make_tag(y, r);
modify(lca(l, r));
modify(lca(l, r));
x = l; y = r;
}
for(int i=1;i<=k;i++) printf("%lld\n", res[i]);
return 0;
}


ytczy666
2个月前

### 博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$

$\;$

## 引入

$\;$

$\;$

# 普通莫队

$\;$

## 核心

$\;$

$n,m\leq 10^5$

$\;$

## 时间复杂度

$\;$

(注意：这里我们假设m与n同阶)
$\;$

$\;$

$\;$

$\;$

$\;$

## Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
int pos, l, r;
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块
return a.r < b.r; // 右端点所属位置
}
int main() {
scanf("%d", &n);
sq = (int)sqrt(n);
for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号
for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
std::sort(b + 1, b + n + 1);
nn = std::unique(b + 1, b + n + 1) - b - 1;
for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
//----------------- 上面是离散化部分，不多赘述
scanf("%d", &m);
std::sort(ask + 1, ask + m + 1, cmp);
int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针
for(int i=1;i<=m;i++) {
int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点
while(x < l) { // 左端点向右移，区间缩小
cnt[a[x]] --; if(!cnt[a[x]]) -- res;
x ++;
}

while(x > l) { // 左端点向左移，区间变大
cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
x --;
}

while(y < r) { // 右端点向右移，区间变大
cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
y ++;
}

while(y > r) { // 右端点向左移，区间缩小
cnt[a[y]] --; if(!cnt[a[y]]) -- res;
y --;
}

ans[ask[i].pos] = res; // 注意：i是排序后区间的编号，但并不是输入时询问的编号
}
for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
return 0;
}


# 带修莫队

$\;$

$\;$

## 时间复杂度

$\;$

$\;$

$\;$

$\;$

## Code

$\;$

https://www.luogu.com.cn/problem/P1903

#include <bits/stdc++.h>

#define fi first
#define se second
const int N = 143333;
int n, m, k, a[N], cnt[N * 10], ans[N], id[N], sq, T, b[N], res, x, y;
std::pair<int,int> cur[N], fur[N];
struct node {
int l, r, t, pos;

bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
if(id[a.r] != id[b.r]) return id[a.r] < id[b.r];
return a.t < b.t;
}

bool g(int d) {
return (x <= d && d <= y);
}
void gg(int x, int y) {
cnt[x] --; cnt[y] ++;
if(!cnt[x]) -- res; if(cnt[y] == 1) ++ res;
}
int main() {
scanf("%d%d", &n, &m);
sq = pow(n, 3.0 / 4);
for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq);
for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
for(int i=1;i<=m;i++) {
char op[5]; int l, r;
scanf("%s", op);
scanf("%d%d", &l, &r);
if(op[0] == 'Q') {
++ k; ask[k].l = l; ask[k].r = r; ask[k].t = i; ask[k].pos = k;
}
else {
cur[i].fi = l; cur[i].se = r;
fur[i].fi = l; fur[i].se = b[l]; b[l] = r;
}
}
std::sort(ask + 1, ask + k + 1, cmp);
int ti = 0;
for(int i=1;i<=k;i++) {
int t = ask[i].t, l = ask[i].l, r = ask[i].r;
while(ti < t) {
if(!cur[ti + 1].fi) {
ti ++; continue;
}
if(g(cur[ti + 1].fi)) gg(a[cur[ti + 1].fi], cur[ti + 1].se);
a[cur[ti + 1].fi] = cur[ti + 1].se;
ti ++;
}
while(ti > t) {
if(!fur[ti].fi) {
ti --; continue;
}
if(g(fur[ti].fi)) gg(a[fur[ti].fi], fur[ti].se);
a[fur[ti].fi] = fur[ti].se;
ti --;
}
while(x < l) {
cnt[a[x]] --; if(!cnt[a[x]]) -- res;
x ++;
}
while(x > l) {
cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
x --;
}
while(y < r) {
cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
y ++;
}
while(y > r) {
cnt[a[y]] --; if(!cnt[a[y]]) -- res;
y --;
}
}
for(int i=1;i<=k;i++) printf("%d\n", ans[i]);
return 0;
}


$\;$

# 树上莫队

$\;$

## 核心

$\;$

$\;$

## Code

$\;$

https://www.luogu.com.cn/problem/P4074
$\;$

#include <bits/stdc++.h>

const int N = 100010;

int n, m, k, q, top, val[N], w[N], tim[N], stk[N], idx, dfn[N], dep[N], S, lst[N], id[N], scc, c[N], bc[N];
int upd[N], pre[N], d[N], x, y, vis[N], f[N][20];
long long ans, res[N];
std::vector<int> G[N];
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
x = x * 10 + c - '0', c = getchar();
return f * x;
}
int dfs(int u, int fa) {
int re = 0;
dfn[u] = ++idx;
f[u][0] = lst[u] = fa;
dep[u] = dep[fa] + 1;
for(int i=1;i<=19;i++) f[u][i] = f[f[u][i - 1]][i - 1];
for(int i=0;i<G[u].size();i++) {
int v = G[u][i];
if(v == fa) continue;
re += dfs(v, u);
if(re >= S) {
scc ++;
while(re)
id[stk[top --]] = scc, re --;
}
}
stk[++top] = u;
return re + 1;
}
struct node {
int l, r, pos, t;
bool cmp(node a, node b) {
if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
if(id[a.r] != id[b.r]) {
if(id[a.l] & 1) return id[a.r] < id[b.r];
return id[a.r] > id[b.r];
}
return a.pos < b.pos;
}
int lca(int x, int y) {
if(x == y) return x;
if(dep[x] < dep[y]) std::swap(x, y);
int ch = dep[x] - dep[y], er = 0;
while(ch) {
if(ch & 1) x = f[x][er];
ch >>= 1; er ++;
}
if(x == y) return x;
for(int i=19;~i;i--) {
if(f[x][i] == f[y][i]) continue;
x = f[x][i]; y = f[y][i];
}
return f[x][0];
}
void change(int d, int v) {
if(vis[d]) {
ans = ans - 1ll * w[tim[c[d]] --] * val[c[d]];
ans = ans + 1ll * w[++ tim[v]] * val[v];
c[d] = v;
}
else c[d] = v;
}
void modify(int x) {
if(vis[x]) {
vis[x] = 0;
ans = ans - 1ll * val[c[x]] * w[tim[c[x]] --];
}
else {
vis[x] = 1;
ans = ans + 1ll * val[c[x]] * w[++tim[c[x]]];
}
}
void make_tag(int u, int v) {
while(u != v) {
if(dep[u] > dep[v]) modify(u), u = f[u][0];
else modify(v), v = f[v][0];
//printf("%d %d\n", u, v);
}
}
int main() {
S = pow(n, 0.666);
for(int i=1;i<=m;i++) val[i] = read();
for(int i=1;i<=n;i++) w[i] = read();
for(int i=1;i<n;i++) {
int u, v;
G[u].push_back(v); G[v].push_back(u);
}
dfs(1, 0);
scc ++;
for(int i=1;i<=n;i++) if(!id[i]) id[i] = scc;
for(int i=1;i<=n;i++) c[i] = read(), bc[i] = c[i];
for(int i=1;i<=q;i++) {
int op, l, r;
if(!op) {
upd[i] = r; d[i] = l; pre[i] = bc[l]; bc[l] = r;
}
else {
if(dfn[l] > dfn[r]) std::swap(l, r);
}
}
std::sort(ask + 1, ask + k + 1, cmp);
if(!upd[i]) continue;
change(d[i], upd[i]);
}
make_tag(x, y); modify(lca(x, y));
modify(lca(x, y));
for(int i=2;i<=k;i++) {
int l = ask[i].l, r = ask[i].r;
// time
int t = ask[i].t, p = ask[i - 1].t;
while(p < t) {
p ++;
if(upd[p]) change(d[p], upd[p]);
}
while(p > t) {
if(upd[p]) change(d[p], pre[p]);
p --;
}
make_tag(x, l);
make_tag(y, r);
modify(lca(l, r));
modify(lca(l, r));
x = l; y = r;
}
for(int i=1;i<=k;i++) printf("%lld\n", res[i]);
return 0;
}


ytczy666
2个月前

## 引入

$\;$

$n\leq 4×10^4$

## 朴素做法

$\;$

## 重心

$\;$

1.点对在某个子树中（直接递归求解）
2.两个点所构成的路径经过了重心G，但你会发现这两个点一定不能在同一个子树中。

3.这条路经的一个端点是G，那么实质上和2.是一种情况，再加入一个$d_G=0$即可
$\;$

## 时间复杂度

$\;$

## Code

$\;$

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
f[u] = 0; // 一定注意初始化
int v = E[i].to;
if(v == fa || vis[v]) continue;
dfs(total, v, u);
f[u] = std::max(f[u], sz[v]);
}
f[u] = std::max(f[u], total - sz[u]);
if(f[u] < mn) {
mn = f[u]; W = u;
}
}
void dfs0(int u, int fa) {
sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值
int v = E[i].to;
if(v == fa || vis[v]) continue;
dfs0(v, u);
sz[u] += sz[v];
}
}
void getG(int rt) {
cnt = 0; // 随时清空
dfs0(rt, 0); // 预处理好每个点的子树大小（因为随着划分重心，树的形态会变化）
mn = 1e9; // 注意初始化
dfs(sz[rt], rt, 0); // DP计算重心
vis[W] = 1; // 这个点作为重心，将其打上标记（相当于一个边界条件）
}
void getd(int u, int fa) {
q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中，这里是以这棵树为重心是的d值，与上面的d不一样
int v = E[i].to;
if(vis[v] || v == fa) continue;
d[v] = d[u] + E[i].val;
getd(v, u);
}
}
void solve(int rt) {
getG(rt);  // 得到重心
if(sz[rt] != n) {
// 对于2.情况，要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的
//但对于一开始整棵树的情况就没必要减了
std::sort(q + 1, q + cnt + 1);
// q里存储的是这棵子树内的d值
// 因为树内点的编号不一定是连续的，所以需要开q这个数组存它
int e1 = 1, e2 = cnt;
for(int e1=1;e1<=cnt;e1++) {
while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举，复杂度是线性的
if(e2 <= e1) break;
ans -= (e2 - e1);
}
}
d[W] = 0; // 重心的d当然是0
cnt = 0; // 一定注意要随时清空
getd(W, 0);
std::sort(q + 1, q + cnt + 1);
int e1 = 1, e2 = cnt;
for(int e1=1;e1<=cnt;e1++) {
while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
if(e2 <= e1) break;
ans += (e2 - e1);
}
int v = E[i].to;
if(!vis[v]) solve(v); // 如果这个点没被打上标记，一定要向下递归
}
}
int main() {
scanf("%d", &n);
for(int i=1;i<n;i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
}
scanf("%d", &k);
solve(1);
printf("%d", ans);
return 0;
}


ytczy666
2个月前

## 引入

$\;$

$n\leq 4×10^4$

## 朴素做法

$\;$

## 重心

$\;$

1.点对在某个子树中（直接递归求解）
2.两个点所构成的路径经过了重心G，但你会发现这两个点一定不能在同一个子树中。

3.这条路经的一个端点是G，那么实质上和2.是一种情况，再加入一个$d_G=0$即可
$\;$

## 时间复杂度

$\;$

## Code

$\;$

#include <bits/stdc++.h>

const int N = 40010;
int n, k, head[N], tot, f[N], mn, W, vis[N], d[N], ans, q[N], cnt, sz[N];
struct node {
int to, nxt, val;
}E[N << 1];
void add(int u, int v, int w) {
E[++tot].to = v; E[tot].nxt = head[u]; E[tot].val = w; head[u] = tot;
}
void dfs(int total, int u, int fa) {
f[u] = 0; // 一定注意初始化
int v = E[i].to;
if(v == fa || vis[v]) continue;
dfs(total, v, u);
f[u] = std::max(f[u], sz[v]);
}
f[u] = std::max(f[u], total - sz[u]);
if(f[u] < mn) {
mn = f[u]; W = u;
}
}
void dfs0(int u, int fa) {
sz[u] = 1; q[++cnt] = d[u]; // 这是在减去2那一部分的时候的d值
int v = E[i].to;
if(v == fa || vis[v]) continue;
dfs0(v, u);
sz[u] += sz[v];
}
}
void getG(int rt) {
cnt = 0; // 随时清空
dfs0(rt, 0); // 预处理好每个点的子树大小（因为随着划分重心，树的形态会变化）
mn = 1e9; // 注意初始化
dfs(sz[rt], rt, 0); // DP计算重心
vis[W] = 1; // 这个点作为重心，将其打上标记（相当于一个边界条件）
}
void getd(int u, int fa) {
q[++cnt] = d[u]; // 在求d值的过程中将其存入q数组中，这里是以这棵树为重心是的d值，与上面的d不一样
int v = E[i].to;
if(vis[v] || v == fa) continue;
d[v] = d[u] + E[i].val;
getd(v, u);
}
}
void solve(int rt) {
getG(rt);  // 得到重心
if(sz[rt] != n) {
// 对于2.情况，要减去在相同子树内(i,j)<=k的个数。这个过程是在递归到这个子树中时进行的
//但对于一开始整棵树的情况就没必要减了
std::sort(q + 1, q + cnt + 1);
// q里存储的是这棵子树内的d值
// 因为树内点的编号不一定是连续的，所以需要开q这个数组存它
int e1 = 1, e2 = cnt;
for(int e1=1;e1<=cnt;e1++) {
while(e2 > e1 && q[e1] + q[e2] > k) e2 --; // 双指针枚举，复杂度是线性的
if(e2 <= e1) break;
ans -= (e2 - e1);
}
}
d[W] = 0; // 重心的d当然是0
cnt = 0; // 一定注意要随时清空
getd(W, 0);
std::sort(q + 1, q + cnt + 1);
int e1 = 1, e2 = cnt;
for(int e1=1;e1<=cnt;e1++) {
while(e2 > e1 && q[e1] + q[e2] > k) e2 --;
if(e2 <= e1) break;
ans += (e2 - e1);
}
int v = E[i].to;
if(!vis[v]) solve(v); // 如果这个点没被打上标记，一定要向下递归
}
}
int main() {
scanf("%d", &n);
for(int i=1;i<n;i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);