SP2666 QTREE4 - Query on a tree IV

    • 127通过
    • 344提交
  • 题目来源 SPOJ 2666
  • 评测方式 RemoteJudge
  • 标签 Link-Cut Tree,LCT 分治 概率论,统计 递归
  • 难度 省选/NOI-
  • 时空限制 646ms / 1536MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    你被给定一棵n个点的带边权的树(边权可以为负),点从1到n编号。每个点可能有两种颜色:黑或白。我们定义dist(a,b)为点a至点b路径上的权值之和。

    一开始所有的点都是白色的。

    要求作以下操作:

    C a 将点a的颜色反转(黑变白,白变黑)

    A 询问dist(a,b)的最大值。a,b点都必须为白色(a与b可以相同),显然如果树上仍存在白点,查询得到的值一定是个非负数。

    特别地,如果作'A'操作时树上没有白点,输出"They have disappeared."。

    Translated by @vegacx

    题目描述

    You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3...,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.

    All the nodes are white initially.

    We will ask you to perfrom some instructions of the following form:

    • C a : change the color of node a.(from black to white or from white to black)
    • A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

    输入输出格式

    输入格式:

    • In the first line there is an integer N (N <= 100000)
    • In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)
    • In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
    • In the next Q lines, each line contains an instruction "C a" or "A"

    输出格式:

    For each "A" operation, write one integer representing its result. If there is no white node in the tree, you should write "They have disappeared.".

    输入输出样例

    输入样例#1: 复制
    3
    1 2 1
    1 3 1
    7
    A
    C 1
    A
    C 2
    A
    C 3
    A
    输出样例#1: 复制
    2
    2
    0
    They have disappeared.
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。