题目名称	2075. [ZLXOI 2015][异次元圣战III]ZLX的陨落
输入输出	`ThefallingofZLX.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	Satoshi 于2015-10-30加入
开放分组	全部用户
提交状态
分类标签	LCA 树链剖分
	分享题解

通过：182，提交：325，通过率：56%
szzy	100	0.151 s	5.45 MiB	C++
Anonymity	100	0.158 s	3.64 MiB	C++
AntiLeaf	100	0.177 s	5.34 MiB	C++
Alex丶Baker	100	0.186 s	24.25 MiB	C++
521	100	0.194 s	2.81 MiB	C++
QVQ	100	0.210 s	2.56 MiB	C++
Alex丶Baker	100	0.210 s	24.25 MiB	C++
Hzoi_Mafia	100	0.240 s	3.17 MiB	C++
Alex丶Baker	100	0.244 s	32.47 MiB	C++
真的菜	100	0.248 s	4.51 MiB	C++

本题关联比赛
ZLXOI2015Day2

关于 ZLX的陨落的近10条评论(全部评论)
居然SB到打树剖！！！都怪@皮皮星 ~玖湫~ 2017-08-15 18:36 18楼
回复 @一個人的雨 : 嗯..我第一次Segtree开小..第二次发现edge也开小了... Fmuckss 2017-06-06 12:50 17楼
AntiLeaf 2017-05-25 15:56 16楼
回复 @小明 : 学习一波 NVIDIA 2016-11-17 16:27 15楼
、小明 2016-11-17 16:26 14楼
数组开小了 AAAAAAAAAA 2016-11-16 21:30 13楼
倍增LCA莫名敲跪。。。。然后只好换树链剖分。。。 asddddd 2016-11-08 20:15 12楼
谁能解释一下为什么我写出来的两个不同的LCA（一个是理论错误的）都能A掉这道题我觉得求LCA时 `while(top[x]!=top[y]){ if(size[top[x]]>size[top[y]])x^=y^=x^=y; x=fa[top[x]];}` 和 `while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]])x^=y^=x^=y; x=fa[top[x]];}` 没什么区别QAQ 安呐一条小咸鱼。 2016-10-16 06:18 11楼
回复 @liu_runda : 这两个题不是多输入一个m就可以过了吗？代码互通 iortheir 2016-09-08 16:44 10楼
好不科学，Tarjan居然比倍增慢QAQ 好吧是我路径压缩写错了导致根本没压缩= = AntiLeaf 2016-08-28 14:18 9楼

2075. [ZLXOI 2015][异次元圣战III]ZLX的陨落

★★ 输入文件：ThefallingofZLX.in 输出文件：ThefallingofZLX.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

正当革命如火如荼，情侣教会日薄西山之时，SOX和FFF的分歧却越来越大，SOX认为情侣教会不合适的、无限制的秀恩爱和阶级歧视值得反对，而FFF认为一切情侣都该从这个世界上消失。

SOX先发制人，率先接管了全国政权并突袭了FFF，暗杀了FFF的首领，FFF的红色革命事业遭到了空前的打击，一些FFF团员积极抵抗，另一些FFF团员隐居避世，而一些FFF团员则走向极端，参加了一个邪恶组织：诅咒教会

你虽然对SOX下山摘桃子的行为不满，但你对邪教更不满。在对诅咒教会的长期调查中，你发现该组织的操纵者是亡灵巫师ZLX！现在，维护正义的使命降到了你身上！你和其他的一些远征军将士前往ZLX的城堡，却掉入了ZLX的魔法陷阱--扭曲虚空，扭曲虚空由n个魔法结界空间组成，m条虚空隧道连接着它们，你和其他的远征军将士（恰好有n个）分散在魔法结界空间里，只有会合在一起，你们才能冲破封锁(扭曲虚空是一颗树)。现在，你向平行世界的你提出了疑问，如果给出两个人会合，总共至少需要多少魔法能量？

已知虚空隧道的长度与消耗的魔法能量在数值上相等。

ZLX的末日已经到临，等到你冲出虚空隧道，亲手结果了ZLX吧！

【输入格式】

第一行一个正整数N，代表魔法结界空间的个数，一个正整数M，代表虚空隧道的个数

接下来M行，每行三个数$u,v,w$，代表虚空隧道连接的两个点和虚空隧道的长度

接下来一个正整数Q，代表查询个数

接下来Q行，每行两个数$u,v$代表询问从$u$到$v$需要消耗的魔法能量

【输出格式】

Q行，每行一个正整数

【样例输入】

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

【样例输出】

15 21 10 15 5

【提示】

对于20%的数据，$n<=300,q<=300$

对于40%的数据,$n<=2000,q<=2000$

对于100%的数据,$n<=100000,q<=100000,w<=32767，m=n-1$