树的深度优先与广度优先离线查询：CSP-J2022山东部署挑战

未分类 5小时前程序员胖胖胖虎阿

4 0 0

树的深度优先与广度优先的离线查询：CSP-J2022山东地区的相关挑战

本文涉及知识点

本文涉及C++图论相关知识、广度优先搜索（BFS）算法以及深度优先搜索（DFS）相关内容。

P11855 [CSP-J2022 山东] 部署

题目背景

受疫情影响，山东省取消了CSP-J 2022的认证活动，并于次年三月重新命题，在省内补办比赛。

题目描述

古代战争中，依靠烽火传信和将军调兵遣将获取优势。A国在n个城市间构建道路与行军部署渠道，形成以1号城市为根节点的树状结构。每个城市有初始兵力，初始时第i个城市兵力为a_i。将军进行m次测试，每次测试为两种命令之一：
- 1 x y：向x号城市及其子树中的所有城市增加y兵力。
- 2 x y：向x号城市及其直接相连的城市（含父节点和子节点）增加y兵力。m次命令执行后，进行q次询问，每次询问x号城市的最终兵力。

输入格式

第一行正整数n表示城市数量。第二行n个正整数表示各城市初始兵力。接下来n-1行，每行两个整数表示城市间直接相连的道路。再一行正整数m表示测试次数，接下来m行是两种测试命令。最后一行正整数q表示询问次数，接下来q行是询问的城市编号。

输出格式

输出q次询问的各城市最终兵力值。

树 DFS BFS 离线查询

执行命令二时，a[x] += y，父节点也加y，cnt2[x] += y；执行命令一时，cnt1[x] += y。通过DFS或BFS保证父节点先处理，确保无后效性。具体为：a[当前节点] += cnt2[父节点]，cnt1[当前节点] += cnt1[父节点]，然后a[当前节点] += cnt1[当前节点]。

核心代码

```cpp

include

using namespace std;

template
std::istream& operator >> (std::istream& in, pair& pr) {
in >> pr.first >> pr.second;
return in;
}

template
std::istream& operator >> (std::istream& in, tuple& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t);
return in;
}

template
std::istream& operator >> (std::istream& in, tuple& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
return in;
}

template
std::istream& operator >> (std::istream& in, tuple& t) {
in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t) >> get<4>(t) >> get<5>(t) >> get<6>(t);
return in;
}

template
vector Read() {
int n;
cin >> n;
vector ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}
template
vector ReadNotNum() {
vector ret;
T tmp;
while (cin >> tmp) {
ret.emplace_back(tmp);
if ('\n' == cin.get()) { break; }
}
return ret;
}

template
vector Read(int n) {
vector ret(n);
for (int i = 0; i < n; i++) {
cin >> ret[i];
}
return ret;
}

template
class COutBuff
{
public:
COutBuff() {
m_p = puffer;
}
template
void write(T x) {
int num[28], sp = 0;
if (x < 0)
*m_p++ = '-', x = -x;

    if (!x)
        *m_p++ = 48;

    while (x)
        num[++sp] = x % 10, x /= 10;

    while (sp)
        *m_p++ = num[sp--] + 48;
    AuotToFile();
}
void writestr(const char* sz) {
    strcpy(m_p, sz);
    m_p += strlen(sz);
    AuotToFile();
}
inline void write(char ch)
{
    *m_p++ = ch;
    AuotToFile();
}
inline void ToFile() {
    fwrite(puffer, 1, m_p - puffer, stdout);
    m_p = puffer;
}
~COutBuff() {
    ToFile();
}

private:
inline void AuotToFile() {
if (m_p - puffer > N - 100) {
ToFile();
}
}
char puffer[N], * m_p;
};

template
class CInBuff
{
public:
inline CInBuff() {}
inline CInBuff& operator>>(char& ch) {
FileToBuf();
while (('\r' == S) || ('\n' == S) || (' ' == S)) { S++; }//忽略空格和回车
ch = S++;
return this;
}
inline CInBuff& operator>>(int& val) {
FileToBuf();
int x(0), f(0);
while (!isdigit(S))
f |= (S++ == '-');
while (isdigit(S))
x = (x << 1) + (x << 3) + (S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return this;
}
inline CInBuff& operator>>(long long& val) {
FileToBuf();
long long x(0); int f(0);
while (!isdigit(S))
f |= (S++ == '-');
while (isdigit(S))
x = (x << 1) + (x << 3) + (S++ ^ 48);
val = f ? -x : x; S++;//忽略空格换行
return this;
}
template
inline CInBuff& operator>>(pair& val) {
this >> val.first >> val.second;
return this;
}
template
inline CInBuff& operator>>(tuple& val) {
this >> get<0>(val) >> get<1>(val) >> get<2>(val);
return this;
}
template
inline CInBuff& operator>>(tuple& val) {
this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);
return this;
}
template
inline CInBuff& operator>>(vector& val) {
int n;
this >> n;
val.resize(n);
for (int i = 0; i < n; i++) {
this >> val[i];
}
return this;
}
template
vector Read(int n) {
vector ret(n);
for (int i = 0; i < n; i++) {
this >> ret[i];
}
return ret;
}
template
vector Read() {
vector ret;
this >> ret;
return ret;
}
private:
inline void FileToBuf() {
const int canRead = m_iWritePos - (S - buffer);
if (canRead >= 100) { return; }
if (m_bFinish) { return; }
for (int i = 0; i < canRead; i++)
{
buffer[i] = S[i];//memcpy出错
}
m_iWritePos = canRead;
buffer[m_iWritePos] = 0;
S = buffer;
int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);
if (readCnt <= 0) { m_bFinish = true; return; }
m_iWritePos += readCnt;
buffer[m_iWritePos] = 0;
S = buffer;
}
int m_iWritePos = 0; bool m_bFinish = false;
char buffer[N + 10], * S = buffer;
};

class CNeiBo
{
public:
static vector> Two(int n, const vector>& edges, bool bDirect, int iBase = 0)
{
vector> vNeiBo(n);
for (const auto& [i1, i2] : edges)
{
vNeiBo[i1 - iBase].emplace_back(i2 - iBase);
if (!bDirect)
{
vNeiBo[i2 - iBase].emplace_back(i1 - iBase);
}
}
return vNeiBo;
}
static vector> Two(int n, const vector>& edges, bool bDirect, int iBase = 0)
{
vector> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
if (!bDirect)
{
vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
}
}
return vNeiBo;
}
static vector>> Three(int n, vector>& edges, bool bDirect, int iBase = 0)
{
vector>> vNeiBo(n);
for (const auto& v : edges)
{
vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
if (!bDirect)
{
vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
}
}
return vNeiBo;
}
static vector>> Three(int n, const vector>& edges, bool bDirect, int iBase = 0)
{
vector>> vNeiBo(n);
for (const auto& [u, v, w] : edges)
{
vNeiBo[u - iBase].emplace_back(v - iBase, w);
if (!bDirect)
{
vNeiBo[v - iBase].emplace_back(u - iBase, w);
}
}
return vNeiBo;
}
static vector> Mat(vector>& neiBoMat)
{
vector> neiBo(neiBoMat.size());
for (int i = 0; i < neiBoMat.size(); i++)
{
for (int j = i + 1; j < neiBoMat.size(); j++)
{
if (neiBoMat[i][j])
{
neiBo[i].emplace_back(j);
neiBo[j].emplace_back(i);
}
}
}
return neiBo;
}
};
class CBFSLeve {
public:
static vector Leve(const vector>& neiBo, vector start) {
vector leves(neiBo.size(), -1);
for (const auto& s : start) {
leves[s] = 0;
}
for (int i = 0; i < start.size(); i++) {
for (const auto& next : neiBo[start[i]]) {
if (-1 != leves[next]) { continue; }
leves[next] = leves[start[i]] + 1;
start.emplace_back(next);
}
}
return leves;
}
template
static vector Leve(int N, NextFun nextFun, vector start) {
vector leves(N, -1);
for (const auto& s : start) {
leves[s] = 0;
}
for (int i = 0; i < start.size(); i++) {
auto nexts = nextFun(start[i]);
for (const auto& next : nexts) {
if (-1 != leves[next]) { continue; }
leves[next] = leves[start[i]] + 1;
start.emplace_back(next);
}
}
return leves;
}
static vector> LeveNodes(const vector& leves) {
const int iMaxLeve = max_element(leves.begin(), leves.end());
vector> ret(iMaxLeve + 1);
for (int i = 0; i < leves.size(); i++) {
ret[leves[i]].emplace_back(i);
}
return ret;
};
static vector LeveSort(const vector& leves) {
const int iMaxLeve = max_element(leves.begin(), leves.end());
vector> leveNodes(iMaxLeve + 1);
for (int i = 0; i < leves.size(); i++) {
leveNodes[leves[i]].emplace_back(i);
}
vector ret;
for (const auto& v : leveNodes) {
ret.insert(ret.end(), v.begin(), v.end());
}
return ret;
};
};
class Solution {
public:
vector Ans(vector& a, vector>& edge, vector>& ope, vector& que) {
const int N = a.size();
auto neiBo = CNeiBo::Two(N, edge, false, 1);
auto leves = CBFSLeve::Leve(neiBo, { 0 });
vector par(N, -1);
for (int i = 0; i < N; i++) {
for (const auto& next : neiBo[i]) {
if (leves[i] < leves[next]) {
par[next] = i;
}
}
}
vector cnt1(N), cnt2(N);
for (auto [kind, x, y] : ope) {
x--;
if (2 == kind) {
a[x] += y;
if (-1 != par[x]) {
a[par[x]] += y;
}
cnt2[x] += y;
}
else {
cnt1[x] += y;
}
}
auto leveNodes = CBFSLeve::LeveSort(leves);
for (const auto& cur : leveNodes) {
if (-1 !=