题解 | B、Eezie and Pie
Array
https://ac.nowcoder.com/acm/contest/33191/A
前言
不会倍增不会树刨不会树上差分，然后自己想了个On的解法过了（虽然事后有佬说我这个和树上差分差不多）但没有什么前置知识，只要会dfs就行。然后赛时debug了两小时都是wa，正当崩溃的时候才发现题目没有保证给的边（u,v)一定是u到v的单向边，遂改成双向边，就AC了（哭）。
题意
有一个以1为根节点的树，树有n个节点，每个节点有一个最大移动距离di，表示他们只能向上移动di个点，走到根节点为止（只能往上走，不能转方向去往别的子树），问对于每个点，有多少点能够到达它（包括自己）。
样例解释
输入
10
1 2
2 3
2 4
3 5
4 6
4 7
1 8
8 9
8 10
0 0 1 2 2 5 3 1 0 2
输出
6 6 2 3 1 1 1 2 1 1
构造树后如图：（黑色是id，红色是di）
- 对于点1：能到达它的点有：1、4、6、7、8、10；
- 对于点2：有：2 3 4 5 6 7；
- 对于点3：有：3 5；
- 对于点4：有：4、6、7；
- 对于点5：有：5；
- 对于点6：有：6；
- 对于点7：有：7；
- 对于点8：有：8、10；
- 对于点9：有：9；
- 对于点10：有10；
所以答案为：6 6 2 3 1 1 1 2 1 1
初始想法
一开始想的是按照题意记录每个点能有多少个点走到它，但是想了想感觉我写不出来，于是换了个角度。
我们记录每个点能走到哪些点上。
比如对于点5，从根节点到它的路径是：1、2、3、5，点5能向上走两个点，所以它能走到的点就是：2、3、5.我们可以用一个数组或者哈希表记录每个点的出现次数。最后结果就是每个点的出现次数。
我们dfs跑一遍树，过程中用一个vector来记录路径，到达一个新的点后，根据它的di，我们从后往前遍历路径，即看这个点能走到哪些点上，用数组记录出现次数。
时间复杂度：dfs遍历n个点用时On,每个点都要遍历一遍路径，时间复杂度On，总复杂度n^2.
很明显，寄的很彻底。
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e6 + 50, MOD = 998244353;
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)res = (1LL) * res * a % MOD;
b >>= 1;
a = (1LL) * a * a % MOD;
}
return res;
}
//记录树
vector<int>tree[N];
//mymove记录每个点的di，cnt记录结果，anvenue记录路径
vector<int>mymove(N), cnt(N), avenue;
//记录路径长度
int len;
void dfs(int x, int y)
{
//逆着遍历路径
for (int i = len - 1; i >= 0; i--)
{
//记录每个点的出现次数
cnt[avenue[i]]++;
//当这个点不能再往上走时，结束遍历
if (mymove[x] == 0)break;
else mymove[x]--;
}
for (auto i : tree[x])
{
//y是x的父节点，因为我们双向建图，要防止儿子dfs到父亲上
if (i != y)
{
//更新路径
avenue.push_back(i);
len++;
dfs(i, x);
len--;
avenue.pop_back();
}
}
}
void solve()
{
int n, x, y;
cin >> n;
for (int i = 1; i < n; i++)
{
cin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}
for (int i = 1; i <= n; i++)cin >> mymove[i];
//初始根节点
avenue.push_back(1);
len = 1;
dfs(1, 0);
//输出结果
for (int i = 1; i <= n; i++)cout << cnt[i] << " ";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
solve();
return 0;
}
优化
重点在于我们每个点都要遍历一遍路径，太费时间了，该怎么优化掉呢。
可以注意到，我们遍历路径都是从后往前遍历，而当我们dfs在当前点结束操作时，会回溯到上一个点，这不正和我们遍历路径的操作一样吗。
所以我们可以不在每个点上都遍历一遍路径，而是在回溯的过程中实现这一步骤，这样时间复杂度就只剩下dfs的On了。
但遍历路径我们可以根据di的大小来判断是否能走到下一个点，回溯时我们该怎么操作？
每个点最多能往上走di个位置，因为路径是不变的，所以对于第i个点，它们最终会停在向上第di个点上，之后的点就无法走到了。
我们可以用一个数组ans，ans[i]的意思是，对于第i个点，最多有几个点是以他为重点的。比如点5的终点就是点2.
当我们向下dfs时，每经过一个点，都记录下它能走到的最远的点，这部分可以通过存储的路径得到。同时权值++。当我们回溯时，把这个权值直接加到当前点的cnt数组上，代表这个树往下最多有这么多的点能够走到它。当离开这个点时，把权值减去ans[i]（这一部分的点所提供的权值不能再影响到后面点的更新上，因为这一部分点走不到更上面的点了）。
这样，我们就可以在一趟dfs中求的结果。
时间复杂度：dfs一遍所有点：On。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>
#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e6 + 50, MOD = 998244353;
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)res = (1LL) * res * a % MOD;
b >>= 1;
a = (1LL) * a * a % MOD;
}
return res;
}
vector<int>tree[N];
vector<int>mymove(N), cnt(N), avenue, ans(N);
int len;
int dfs(int x, int y)
{
//记录当前点的权值
int temp = 1;
//在路径中找到这个点所能到达的最高点
int st = max((ll)0, len - mymove[x] - 1);
ans[avenue[st]]++;
for (auto i : tree[x])
{
if (i != y)
{
avenue.push_back(i);
len++;
//当前点的权值加上子节点传来的权值
temp += dfs(i, x);
len--;
avenue.pop_back();
}
}
//权值为多少，说明这个子树有多少个点能走到他
cnt[x] = temp;
//减去以这个点为终点的点的权值
temp -= ans[x];
ans[x] = 0;
//将当前点的权值加到父节点上
return temp;
}
void solve()
{
int n, x, y;
cin >> n;
for (int i = 1; i < n; i++)
{
cin >> x >> y;
tree[x].push_back(y);
tree[y].push_back(x);
}
for (int i = 1; i <= n; i++)cin >> mymove[i];
avenue.push_back(1);
len = 1;
dfs(1,0);
for (int i = 1; i <= n; i++)cout << cnt[i] << " ";
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--)
solve();
return 0;
}
比亚迪成长空间 168人发布
