每日一题 7月30日Xor Path 树上路径异或

题目链接:https://ac.nowcoder.com/acm/problem/20857
图片说明

思路:我们考虑每个点的经过次数就可以了。
1:u到其他所有点 n-1
2:u的子树之间
3:u的子树到除u的其他点(父节点以上)

#include<bits/stdc++.h>
#define LL long long
using namespace std;

vector<int> G[500005];
int a[500005];
LL siz[500005];
int n, ans=0;
void DFS(int u, int fa) {

    LL sum=n-1;//1
    for(auto to: G[u]) {
        if(to!=fa) {
            DFS(to, u);
            sum+=siz[u]*siz[to];//2
            siz[u]+=siz[to];
        }
    }

    sum+=siz[u]*(n-siz[u]-1);//3
    siz[u]++;
    if(sum%2) {
        ans^=a[u];
    }
}

int main() {

    int x, y;
    scanf("%d", &n);
    for(int i=1; i<n; i++) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i=1; i<=n; i++) {
        scanf("%d", &a[i]);
    }
    DFS(1, 0);
    printf("%d\n", ans);

    return 0;
}
全部评论

相关推荐

04-10 11:56
如皋中学 Java
高斯林的信徒:双c9能简历挂的?
点赞 评论 收藏
分享
神哥不得了:神哥来啦~1.建议不要包装,很容易问穿2.没日常也能找到暑期3.简历模板换一下,字体和版式看着好难受,而且最好压缩到一页,技术的倒数第2和3重复啦,项目建议换两个高质量的上去,如果时间够的话,八股就把高频top50的题目多巩固几遍,吃透,注意不要找假高频,这样绝对能找到暑期
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务