C++ 解法, 执行用时: 319ms, 内存消耗: 49800K, 提交时间: 2021-12-12 17:08:17
/*************************************************************************
> File Name: std.cpp
> Author: ghost_lzw
> Mail: lanzongwei@gmail.com
> Created Time: 一 12/ 6 10:27:11 2021
************************************************************************/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#ifdef DEBUG
void err(std::istream_iterator<std::string>){}
template<typename T, typename... Args>
void err(std::istream_iterator<std::string> it, T a, Args... args) {
std::cerr << *it << " = " << a << ' ';
err(++it, args...);
}
#define debug(args...) {std::string _s=#args;std::replace(_s.begin(), _s.end(),',',' ');\
std::cerr<<"DEBUG:";std::istringstream it(_s);\
err(std::istream_iterator<std::string>(it), args);std::cerr<<std::endl;}
#else
#define debug(...)
#endif
template<typename T>
std::ostream& operator << (std::ostream& out, const std::vector<T>& v) {
out << "{ ";
for (auto& i : v) out << i << ' ';
out << "} ";
return out;
}
template<typename InfoCollector=std::nullptr_t, typename Info = int>
struct HLD {
std::vector<int> fa, dep, siz, son;
std::vector<int> top, dfn, rnk; int cnt;
using Tree = std::vector<std::vector<int>>;
const Tree &g;
InfoCollector collector;
void dfs1(int u) {
son[u] = -1; siz[u] = 1;
for (const auto& i : g[u]) if (!dep[i]) {
dep[i] = dep[u] + 1;
fa[i] = u;
dfs1(i);
siz[u] += siz[i];
if (son[u] == -1 or siz[i] > siz[son[u]]) son[u] = i;
}
}
void dfs2(int u, int f) {
top[u] = f; dfn[u] = cnt; rnk[cnt++] = u;
if (!~son[u]) return ;
dfs2(son[u], f);
for (const auto& i : g[u]) if (i != son[u] and i != fa[u])
dfs2(i, i);
}
HLD(const Tree& g, int rt=0) :
fa(g.size()), dep(g.size(), 0), siz(g.size()), son(g.size()),
top(g.size()), dfn(g.size()), rnk(g.size()),
cnt(0), g(g) {
dep[rt] = 1; fa[rt] = -1;
dfs1(rt); dfs2(rt, rt);
}
int LCA(int u, int v) const {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) std::swap(u, v);
v = fa[top[v]];
}
return dep[u] > dep[v] ? v : u;
}
template<typename = std::enable_if<!std::is_same<InfoCollector,
std::nullptr_t>::value>>
void buildInfo() {
collector = InfoCollector(cnt);
}
template<typename = std::enable_if<!std::is_same<InfoCollector,
std::nullptr_t>::value>>
void modify(int u, int v, Info val) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) std::swap(u, v);
collector.rangeModify(dfn[top[v]], dfn[v] + 1, val);
v = fa[top[v]];
}
if (dep[u] > dep[v]) std::swap(u, v);
collector.rangeModify(dfn[u], dfn[v] + 1, val);
}
Tree& vtree(std::vector<int>& key, int* rt = nullptr) const {
static Tree vt(cnt);
static std::vector<int> st(cnt);
int top = -1; vt[0].clear();
std::sort(key.begin(), key.end(), [&](int a, int b) {return dfn[a] < dfn[b];});
int mx = dfn[key[0]];
if (rt) *rt = key[0];
static std::function<void(int, int)> add = [&] (const int& u, const int& v) {
if (rt and dfn[u] < mx) mx = dfn[u], *rt = u;
vt[u].emplace_back(v);
};
static std::function<void(int)> insert = [&] (int x) {
vt[x].clear();
if (top < 0) {st[++top] = x; return ;}
int lca = LCA(x, st[top]);
if (lca == st[top]) st[++top] = x;
else {
while (top > 0 and dfn[st[top - 1]] >= dfn[lca])
add(st[top - 1], st[top]), --top;
if (lca != st[top]) vt[lca].clear(), add(lca, st[top]), st[top] = lca;
st[++top] = x;
}
};
for (const auto& i : key) insert(i);
while (top > 0) add(st[top - 1], st[top]), --top;
return vt;
}
};
template<typename Info>
struct FenwickRange {
static int lowbit(int x) {return x & -x;}
int n;
std::vector<Info> info;
FenwickRange() = default;
FenwickRange(int n)
: n(n),
info(n + 1, {0}) {}
void modify(int x, const Info& v) {
for (++x; x <= n; x += lowbit(x)) info[x] += v;
}
Info querry(int x) {
Info s{0};
for (++x; x; x -= lowbit(x)) s += info[x];
return s;
}
void rangeModify(int l, int r, const Info& x) { modify(l, x), modify(r, -x); }
};
namespace std {
std::array<int, 19>& operator += (std::array<int, 19> &a,
const std::array<int, 19> &b) {
for (int i = 0; i < 19; i++) a[i] += b[i];
return a;
}
std::array<int, 19> operator + (const std::array<int, 19> &a,
const std::array<int, 19> &b) {
std::array<int, 19> res;
for (int i = 0; i < 19; i++) res[i] = a[i] + b[i];
return res;
}
std::array<int, 19> operator - (const std::array<int, 19> &a) {
std::array<int, 19> res;
for (int i = 0; i < 19; i++) res[i] = -a[i];
return res;
}
}
using Info = std::array<int, 19>;
std::ostream& operator << (std::ostream& out, const Info& v) {
out << "[ ";
for (int i = 0; i < 19; i++) out << v[i] << ' ';
out << "] ";
return out;
}
struct InfoCollector : FenwickRange<Info> {
using FenwickRange<Info>::FenwickRange;
void rangeModify(int l, int r, int v) {
Info res; std::fill(res.begin(), res.end(), 0);
int f = v < 0 ? -1 : 1;
res[18] = f;
v = abs(v);
for (int i = 0; i < 18; i++)
if (v & (1 << i)) res[i] = f;
FenwickRange<Info>::rangeModify(l, r, res);
}
};
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
int n, m; std::cin >> n >> m;
std::vector<int> c(n);
std::vector<std::vector<int>> world(10);
std::array<int, 10> which;
for (int i = 0; i < n; i++)
std::cin >> c[i], world[c[i]].emplace_back(i);
std::vector<int> v(n);
for (int i = 0; i < n; i++) std::cin >> v[i];
std::vector<std::vector<int>> g(n);
for (int i = 0, u, v; i < n - 1; i++) {
std::cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
HLD hld(g);
std::vector<std::pair<__gnu_pbds::gp_hash_table<int, int>, HLD<InfoCollector>>> info;
std::vector<std::vector<int>> tr;
for (int i = 0; i < 10; i++) if (!world[i].empty()) {
int rt;
auto& vt = hld.vtree(world[i], &rt);
which[i] = info.size();
tr.clear();
__gnu_pbds::gp_hash_table<int, int> mp;
int cnt{0};
std::function<int(int)> gen = [&] (int u) {
mp[u] = cnt; int id = cnt++; tr.emplace_back();
tr[id].reserve(vt[u].size());
for (auto& j : vt[u]) {
int p = gen(j);
tr[id].emplace_back(p);
}
return id;
};
gen(rt);
info.emplace_back(mp, tr);
auto &hld = info.back().second;
hld.buildInfo();
for (auto& j : world[i]) hld.modify(0, mp[j], v[j]);
}
while (m--) {
int op; std::cin >> op;
if (op == 1) {
int a, x; std::cin >> a >> x;
auto& [mp, hld] = info[which[c[a]]];
hld.modify(0, mp[a], -v[a]);
v[a] = x;
hld.modify(0, mp[a], v[a]);
} else {
int b; std::cin >> b;
int64_t ans{0};
for (auto& [mp, hld] : info) if (mp.find(b) != mp.end()) {
std::array<int, 19> res = hld.collector.querry(hld.dfn[mp[b]]);
for (int i = 0; i < 18; i++) {
if (v[b] & (1 << i)) ans += (1ll << i) * (res[18] - res[i]);
else ans += (1ll << i) * res[i];
}
}
std::cout << ans << '\n';
}
}
return 0;
}
个世界，每个世界可能是魔法世界，修真世界...，世界树上最多有 
种世界。
的能量脉冲。)
的能量脉冲第一次碰撞在一起时, 会分别在发生碰撞的世界 
留下
和 
的能量脉冲残留值，同一脉冲在一个世界发生多次碰撞只会产生一次能量残留。脉冲的起始点为发送脉冲的世界，终止点为世界树根，起始点和终止点都有可能发生碰撞。
次动荡，动荡有两种类型。
将世界 
的能量脉冲留下的残留清除，重新发送一个能量值为 
的能量脉冲。
询问世界 
的残留能量值。，代表有
个数
代表世界
的类型。
代表世界
行，每一行
, 代表世界
和世界
为世界树根。
。
的询问，输出一行整数，代表对应世界的能量残留值