「LAOI-1」小熊游景点

Luogu

IDLGP9487

Time1000ms

Memory512MB

DifficultyP5

线段树倍增洛谷原创O2优化树形 DP树链剖分ST 表分类讨论

小熊的地图上有 $n$ 个景点，每个景点有分数 $s_i$。 $n-1$ 个点对之间有双向直达的公交线路，每条线路有收费 $w_i$。现在小熊在 $a$ 景点，总司令在 $b$ 景点，他们要**沿简单路径**在 $a\to b$ 路径上的 $p$ 景点汇合，然后**沿简单路径**一起去 $q$ 景点。（$q$ 为任意点，每个人不会游览两次 $p$ 景点） $m$ 次询问，给定 $a,b$，求 $p,q$，使得小熊和总司令花费之和最小的前提下他们经过的景点分数之和最大，输出他们经过的景点分数之和。（指小熊经过的景点分数之和 $+$ 总司令经过的景点分数之和） **重复经过的线路收费重复计算，重复经过的景点分数重复计算。** ## Input 第一行两个整数 $n,m$。分别表示景点个数和询问次数。接下来一行 $n$ 个整数第 $i$ 个整数 $s_i$ 表示第 $i$ 个景点的权值。接下来 $n-1$ 行，每行 $3$ 个整数 $u,v,w$，表示 $u$ 节点和 $v$ 节点之间有一条收费 $w$ 的双向公交路线。接下来 $m$ 行，每行两个整数 $a$ 和 $b$，表示小熊和总司令所在的景点位置。 ## Output 对于每组询问，每行输出一个整数表示结果。 [samples] ## Note ### 样例说明对于第一组样例，小熊的地图如图所示： ![](https://cdn.luogu.com.cn/upload/image_hosting/ktyzyrx7.png) 其中 $a=4,b=7$，令 $p=3,q=6$。小熊的路径为 $4\to2\to1\to3\to6$，花费之和为 $1+3+6+(-4)=6$，景点分数之和为 $1+1+1+1+1=5$。总司令的路径为 $7\to3\to6$，花费之和为 $5+(-4)=1$，景点分数之和为 $1+1+1=3$。小熊和总司令花费之和为 $6+1=7$，经过的景点分数之和为 $5+3=8$。可以证明此时小熊和总司令花费之和最小的前提下他们经过的景点分数之和最大。 ------------ ### 数据范围 **本题采用捆绑测试。** | Subtask | $n,m$ | $s_i,w_i$ | 特殊性质 | 分数 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $=3\times10^5$ | $\in\lbrack0,10^6\rbrack$ | 无 | $10$ | | $2$ | $=3\times10^5$ | $\in\lbrack-10^6,10^6\rbrack$ | 小熊的地图是一条链 | $10$ | | $3$ | $=3\times10^2$ | $\in\lbrack-10^6,10^6\rbrack$ | 无 | $5$ | | $4$ | $=3\times10^3$ | $\in\lbrack-10^6,10^6\rbrack$ | 无 | $15$ | | $5$ | $\le 3\times10^5$ | $\in\lbrack-10^6,10^6\rbrack$ | 无 | $60$ | 对于 $100\%$ 的数据，$1\le n,m\le 3\times 10^5$，$\vert s_i\vert,\vert w_i\vert\le10^6$，小熊的地图是一棵树。（小熊都可以游览景点了，公交价格和景点分数怎么不可以是负数呢？）

Samples

Input #1

7 1
1 1 1 1 1 1 1
1 2 3
3 6 -4
2 5 2
1 3 6
2 4 1
3 7 5
4 7

Output #1

Input #2

10 10
786755 -687509 368192 154769 647117 -713535 337677 913223 -389809 -824004 
1 2 -785875
1 3 -77082
1 4 -973070
3 5 -97388
2 6 -112274
3 7 657757
4 8 741733
3 9 5656
4 10 -35190
3 3
3 10
7 3
5 1
2 10
10 10
1 6
7 2
8 9
9 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "「LAOI-1」小熊游景点",
    "description": {
      "content": "小熊的地图上有 $n$ 个景点，每个景点有分数 $s_i$。 $n-1$ 个点对之间有双向直达的公交线路，每条线路有收费 $w_i$。 现在小熊在 $a$ 景点，总司令在 $b$ 景点，他们要**沿简单路径**在 $a\\to b$ 路径上的 $p$ 景点汇合，然后**沿简单路径**一起去 $q$ 景点。（$q$ 为任意点，每个人不会游览两次 $p$ 景点） $m$ 次询问，给定 $a,b$，",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9487"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小熊的地图上有 $n$ 个景点，每个景点有分数 $s_i$。\n\n$n-1$ 个点对之间有双向直达的公交线路，每条线路有收费 $w_i$。\n\n现在小熊在 $a$ 景点，总司令在 $b$ 景点，他们要**沿简单路径**在 $a\\to b$ 路径上的 $p$ 景点汇合，然后**沿简单路径**一起去 $q$ 景点。（$q$ 为任意点，每个人不会游览两次 $p$ 景点）\n\n$m$ 次询问，给定 $a,b$，...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments