考场上
先开 T1，emmm，感觉贪心很可做。开 T2，看懂题意 + 手玩样例之后没思路。开 T3，看懂题意 + 手玩样例之后发现暴力修改暴力计算答案有 40pts 还是挺香的，写了个暴力。
回头看 T1，想起几分钟之前大佬说 9! 暴搜，有点犹豫写贪心还是暴搜，因为不保证自己贪心的正确性打算放最后写。
看 T2 没思路，会 40pts 的暴力，写了。
T1 想暴搜，枚举全排列，怎么判断和原序列相比交换了几次？我淦，想不出来。写了个看似正确能过样例的贪心，跑路了。
预计得分：100 + 40 + 40 = 180
实际的分：0 + 40 + 40 = 80
出题人太狠了，把贪心卡的一分没有。。。
T1
T2
T3
考场上的代码
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 50001
const int mod = 2019;
int ans, n, m, pthn, head[MAXN], dep[MAXN];
int fa[MAXN][21], lg[MAXN], size[MAXN];
struct Edge {
int next, to, w;
}pth[MAXN];
void add(int from, int to, int w) {
pth[++pthn].to = to, pth[pthn].next = head[from];
pth[pthn].w = w, head[from] = pthn;
}
void dfs(int u) {
dep[u] = dep[fa[u][0]] + 1, size[u] = 1;
for (int i = head[u]; i; i =pth[i].next) {
int x = pth[i].to;
if (x != fa[u][0]) {
dfs(x);
size[u] += size[x];
}
}
}
void dfs1(int u, int k) {
for (int i = head[u]; i; i = pth[i].next) {
int x = pth[i].to;
if (x != fa[u][0]) {
dfs1(x, k);
ans = (1ll * ans + 1ll * (size[k] - size[x]) * size[x] * pth[i].w % mod) % mod;
}
}
}
bool dfs2(int u, int x, int y, int k) {
bool flag = false;
for (int i = head[u]; i; i = pth[i].next) {
int v = pth[i].to;
if (dfs2(v, x, y, k)) {
pth[i].w = (1ll * pth[i].w + k) % mod;
flag = true;
}
}
if (u == x || u == y) return true;
return flag;
}
int lca(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
while (dep[x] > dep[y]) {
x = fa[x][lg[dep[x] - dep[y]] - 1];
}
if (x == y) return x;
for (int k = lg[dep[x]] - 1; k >= 0; --k) {
if (fa[x][k] != fa[y][k]) {
x = fa[x][k];
y = fa[y][k];
}
}
return fa[x][0];
}
int main() {
freopen("network.in", "r", stdin);
freopen("network.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 2, w; i <= n; ++i) {
scanf("%d %d", &fa[i][0], &w);
add(fa[i][0], i, w);
}
for (int i = 1; i <= n; ++i) {
lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
}
dfs(1);
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i <= n; ++i) {
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
}
std::string opt;
for (int i = 1, x, y, k; i <= m; ++i) {
std::cin >> opt >> x;
if (opt == "INC") {
std::cin >> y >> k;
int l = lca(x, y);
dfs2(l, x, y, k);
}
else {
ans = 0;
dfs1(x, x);
printf("%d
", ans % mod);
}
}
fclose(stdin), fclose(stdout);
return 0;
}
正解
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 50001
void read(int &T) {
int x = 0;
bool f = 0;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = !f;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
T = f ? -x : x;
}
void write(int x) {
if (x < 0) putchar('-'), write(-x);
else {
if (x / 10) write(x / 10);
putchar(x % 10 + '0');
}
}
const int mod = 2019;
int n, q, size[MAXN], w[MAXN], pre[MAXN], dfn[MAXN];
namespace Seg {
#define lson now << 1
#define rson now << 1 | 1
struct Node {
int l, r, sizz, siz;
int sizw, sizzw, lazy;
}tree[MAXN << 2];
void build(int l, int r, int now) {
tree[now].l = l, tree[now].r = r;
if (tree[now].l == tree[now].r) {
tree[now].siz = size[pre[l]] % mod;
tree[now].sizz = size[pre[l]] * size[pre[l]] % mod;
tree[now].sizw = size[pre[l]] * w[pre[l]] % mod;
tree[now].sizzw = w[pre[l]] * tree[now].sizz % mod;
return;
}
int mid = (tree[now].l + tree[now].r) >> 1;
build(l, mid, lson), build(mid + 1, r, rson);
tree[now].sizz = (tree[lson].sizz + tree[rson].sizz) % mod;
tree[now].siz = (tree[lson].siz + tree[rson].siz) % mod;
tree[now].sizw = (tree[lson].sizw + tree[rson].sizw) % mod;
tree[now].sizzw = (tree[lson].sizzw + tree[rson].sizzw) % mod;
}
void pushdown(int now) {
if (tree[now].l == tree[now].r) return;
tree[lson].lazy = (tree[lson].lazy + tree[now].lazy) % mod;
tree[rson].lazy = (tree[rson].lazy + tree[now].lazy) % mod;
tree[lson].sizw = (tree[lson].sizw + tree[lson].siz * tree[now].lazy) % mod;
tree[lson].sizzw = (tree[lson].sizzw + tree[lson].sizz * tree[now].lazy % mod) % mod;
tree[rson].sizw = (tree[rson].sizw + tree[rson].siz * tree[now].lazy) % mod;
tree[rson].sizzw = (tree[rson].sizzw + tree[rson].sizz * tree[now].lazy % mod) % mod;
tree[now].lazy = 0;
}
void update(int x, int y, int k, int now) {
if (tree[now].l >= x && tree[now].r <= y) {
tree[now].lazy = (tree[now].lazy + k) % mod;
tree[now].sizw = (tree[now].sizw + tree[now].siz * k % mod) % mod;
tree[now].sizzw = (tree[now].sizzw + tree[now].sizz * k % mod) % mod;
return;
}
if (tree[now].lazy != 0) pushdown(now);
int mid = (tree[now].l + tree[now].r) >> 1;
if (x <= mid) update(x, y, k, lson);
if (y > mid) update(x, y, k, rson);
tree[now].sizw = (tree[lson].sizw + tree[rson].sizw) % mod;
tree[now].sizzw = (tree[lson].sizzw + tree[rson].sizzw) % mod;
}
int query1(int x, int y, int now) {
if (tree[now].l >= x && tree[now].r <= y) {
return tree[now].sizw;
}
if (tree[now].lazy != 0) pushdown(now);
int mid = (tree[now].l + tree[now].r) >> 1, ans = 0;
if (x <= mid) ans = (ans + query1(x, y, lson)) % mod;
if (y > mid) ans = (ans + query1(x ,y, rson)) % mod;
return ans;
}
int query2(int x, int y, int now) {
if (tree[now].l >= x && tree[now].r <= y) {
return tree[now].sizzw;
}
if (tree[now].lazy != 0) pushdown(now);
int mid = (tree[now].l + tree[now].r) >> 1, ans = 0;
if (x <= mid) ans = (ans + query2(x, y, lson)) % mod;
if (y > mid) ans = (ans + query2(x ,y, rson)) % mod;
return ans;
}
}
namespace Cut {
int pthn, head[MAXN], fa[MAXN];
int cnt, dep[MAXN], son[MAXN], top[MAXN];
struct Edge {
int next, to, w;
}pth[MAXN];
void add(int from, int to, int w) {
pth[++pthn].to = to, pth[pthn].next = head[from];
pth[pthn].w = w, head[from] = pthn;
}
void dfs1(int u, int father) {
fa[u] = father, dep[u] = dep[father] + 1, size[u] = 1;
for (int i = head[u]; i; i = pth[i].next) {
int x = pth[i].to;
if (x != fa[u]) {
w[x] = pth[i].w;
dfs1(x, u), size[u] += size[x];
if (size[son[u]] < size[x]) son[u] = x;
}
}
}
void dfs2(int u, int tp) {
top[u] = tp, dfn[u] = ++cnt, pre[cnt] = u;
if (son[u]) dfs2(son[u], tp);
for (int i = head[u]; i; i = pth[i].next) {
int x = pth[i].to;
if (x != fa[u] && x != son[u]) dfs2(x, x);
}
}
void change(int x, int y, int k) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
Seg::update(dfn[top[x]], dfn[x], k, 1);
x = fa[top[x]];
}
if (dfn[x] > dfn[y]) std::swap(x, y);
Seg::update(dfn[x] + 1, dfn[y], k, 1);
}
int ask(int node) {
int ans1 = size[node] * Seg::query1(dfn[node] + 1, dfn[node] + size[node] - 1, 1) % mod;
int ans2 = Seg::query2(dfn[node] + 1, dfn[node] + size[node] - 1, 1);
return (ans1 - ans2 + mod) % mod;
}
}
int main() {
read(n), read(q);
for (int i = 2, u, w; i <= n; ++i) {
read(u), read(w);
Cut::add(u, i, w);
}
Cut::dfs1(1, 0), Cut::dfs2(1, 1), Seg::build(1, n, 1);
std::string opt;
for (int i = 1, x, y, k; i <= q; ++i) {
std::cin >> opt;
read(x);
if (opt == "INC") {
read(y), read(k);
Cut::change(x, y, k);
}
else {
write(Cut::ask(x));
puts("");
}
}
return 0;
}