SP375 QTREE - Query on a tree

    • 167通过
    • 1.8K提交
  • 题目来源 SPOJ 375
  • 评测方式 RemoteJudge
  • 标签 最近公共祖先,LCA 树链剖分,树剖 线段树
  • 难度 NOI/NOI+/CTSC
  • 时空限制 851ms / 1536MB

题解

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

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给定n个点的树,边按输入顺序编号为1,2,...n-1,要求作以下操作: CHANGE i ti 将第i条边权值改为ti QUERY a b 询问从a点到b点路径上的最大边权

    有多组测试数据,每组数据以DONE结尾

    感谢@vegacx 提供的翻译

    题目描述

    You are given a tree (an acyclic undirected connected graph) with N nodes, and edges numbered 1, 2, 3...N-1.

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

    • CHANGE i ti : change the cost of the i-th edge to ti
      or
    • QUERY a b : ask for the maximum edge cost on the path from node a to node b

    输入输出格式

    输入格式:

    The first line of input contains an integer t, the number of test cases (t <= 20). t test cases follow.

    For each test case:

    • In the first line there is an integer N (N <= 10000),
    • 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 cost c (c <= 1000000),
    • The next lines contain instructions "CHANGE i ti" or "QUERY a b",
    • The end of each test case is signified by the string "DONE".

    There is one blank line between successive tests.

    输出格式:

    For each "QUERY" operation, write one integer representing its result.

    输入输出样例

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