题解 | 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） alt

对于点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;
}