牛客算法周周练2 - 小H和游戏（DFS）

 

链接：https://ac.nowcoder.com/acm/contest/5203/D
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

小H正在玩一个战略类游戏，她可以操纵己方的飞机对敌国的N座城市(编号为1~N)进行轰炸

敌国的城市形成了一棵树，小H会依次进行Q次轰炸，每次会选择一个城市A进行轰炸，和这座城市距离不超过2的城市都会受损(这里距离的定义是两点最短路径上的边数)

轰炸结束后，小H还想知道当前城市A受损的次数
作为游戏的开发者之一，你有义务回答小H的问题

输入描述:

第1行，两个整数N(1≤N≤750000)、Q(1≤Q≤750000)
第2~N行，每行两个整数表示树上的一条边
第N+1~N+Q行，每行一个整数，表示小H这次轰炸的城市

输出描述:

输出Q行，每行一个整数表示这一次轰炸的城市在此次轰炸后共计受损几次

示例1

输入

4 4 
1 2 
2 3 
3 4 
1 
2 
3 
4

输出

1 
2 
3 
3

 

 

对于城市u, 我们考虑用一个fa数组找到城市的祖先fa[u], 它的祖先的祖先就是fa[fa[u]]

num[i][0]表示i点对自身的影响，num[i][1]表示i点对儿子的影响，num[i][2]表示i点对孙子的影响

每次查询我们都直接更新num即可

 

这里要特别注意的是很容易把num[fa[x]][1]++写成num[x][0]++。因为一个点被轰炸，它的兄弟结点肯定全被轰炸。

最后输出的是num[x][0]+num[fa[x]][1]+num[fa[fa[x]]][2]

 

#include <bits/stdc++.h>
typedef long long LL;
#define pb push_back
const int INF = 0x3f3f3f3f;
const double eps = 1e-8;
const int mod = 1e9+7;
const int maxn = 8e5+10;
using namespace std;

vector<int> vt[maxn];
int fa[maxn];
int num[maxn][3];

void DFS(int u,int pre)
{
    fa[u]=pre;
    for(int i=0;i<vt[u].size();i++)
    {
        int v=vt[u][i];
        if(v!=pre) DFS(v,u);
    }
}

int main()
{
    #ifdef DEBUG
    freopen("sample.txt","r",stdin); //freopen("data.out", "w", stdout);
    #endif
    
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        vt[u].pb(v); vt[v].pb(u);
    }
    DFS(1,0);
    for(int i=1;i<=q;i++)
    {
        int x;
        scanf("%d",&x);
        num[fa[fa[x]]][0]++;//爷爷节点对自己影响+1
        num[fa[x]][0]++;//父亲节点对自己影响+1
        num[fa[x]][1]++;//父亲节点对儿子影响+1,注意不要写成num[x][0]++了
        num[x][1]++;//x对儿子节点影响+1
        num[x][2]++;//x对孙子节点影响+1
        printf("%d\n",num[x][0]+num[fa[x]][1]+num[fa[fa[x]]][2]);
    }
    
    return 0;
}

 

 

 

 

 

 

 

-