P3359 改造异或树

    • 16通过
    • 128提交
  • 题目提供者 lzr010506
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定一棵n 个点的树,每条边上都有一个权值。现在按顺序删掉所有的n-1条边,每删掉一条边询问当前有多少条路径满足路径上所有边权值异或和为0。

    输入输出格式

    输入格式:

    第一行一个整数n。

    接下来n-1 行,每行三个整数ai,bi, zi,满足1<= ai, bi <=n,表示树上编号为ai 的点和编号为bi 的点中间连有一条权值为zi 的边。

    接下来一行n-1 个整数,两两之间有一个空格隔开,表示一个1~ n- 1 的排列,表示n - 1 条边的删边顺序。

    输出格式:

    输出n 行,每行一个整数,依次表示删掉第0~ n - 1 条边之后的边权异或和为零的路径数。

    输入输出样例

    输入样例#1: 复制
    4
    1 2 0
    2 3 0
    2 4 0
    3 1 2
    输出样例#1: 复制
    6
    3
    1
    0

    说明

    对于20% 数据,满足n <= 1000。

    对于另外30% 数据,满足所有的zi = 0。

    对于全部数据,满足n <=10^5,0<= zi<= 10^9。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。