wannafly 挑战赛10 小H和游戏

题解：

先利用dfs找出各个节点之间的关系。然后利用一个sum[i][j] 数组 sum[i][0] 表示i这个节点收到影响的次数 sum[i][1]表示i这个节点的儿子们收到影响的次数 sum[i][2]表示i的孙子们受到影响的次数，那么我们

可以用sum[f[f[x]]][2]+sum[f[x]][1]+sum[x][0] 表示x这个点被炸的次数，当要轰炸x的时候，

        sum[f[f[x]]][0]++; // grafa

        sum[f[x]][0]++;// fa

        sum[f[x]][1]++; // x以及x的兄弟们

        sum[x][1]++;// son

        sum[x][2]++; // 
便可以覆盖所有的情况

#include <cstdio>

#include <cstring>

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int n,q;

int f[];

int sum[][];

vector<int> edge[];

void dfs(int pos,int fa)

{

    int len=edge[pos].size();//

    f[pos]=fa;

    for(int i=;i<len;i++)

    {

        int next = edge[pos][i];

        if(next!=fa)

        {

            dfs(next,pos);

        }

    }

}

int main()

{

    cin>>n>>q;

    for(int i=;i<n;i++) edge[i].clear();

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d %d",&x,&y);

        edge[x].push_back(y);

        edge[y].push_back(x);

    }

    dfs(,);

    memset(sum,,sizeof(sum));

    f[]=;

    f[]=;

    while(q--)

    {

        int x;

        cin>>x;

        sum[f[f[x]]][]++;

        sum[f[x]][]++;

        sum[f[x]][]++; // sum[x][0]++ 这么写是错的是因为漏掉了他的兄弟们。。。

        sum[x][]++;

        sum[x][]++;

        cout<<sum[f[f[x]]][]+sum[f[x]][]+sum[x][]<<endl;

    }

    return ;

}

巴特西

wannafly 挑战赛10 小H和游戏

最新文章

热门文章