【小奇模拟赛2】小奇的危机

2016年5月22日1,6410

【题目背景】

小奇驾驶飞船来到了一个奇怪的星球,这个星球的所以城市都在地下,而且由于环境不断恶化,星球上发生了可怕的生化危机。

【问题描述】

星球上有n个城市,标号为1-n,用n-1条双向通道连接,保证任意两个城市能互相到达。

生化危机爆发了!但由于政府安全能力有限,安全区只包括在标号l到r的城市,小奇现在在城市x,它想知道最近的安全城市的距离。

【输入格式】

第一行有1个整数n。

接下来n-1行,每行3个整数u,v,l,表示u,v之间有一条长度为l的双向通道。

接下来1个整数q,表示q次生化危机。

接下来q行,每行3个整数l,r,x,描述一次生化危机。

【输出格式】

输出q行,对于每次生化危机输出1个整数,表示最近安全城市的距离。

【样例输入】

3

1 2 1

1 3 1

3

2 3 1

2 3 2

3 3 2

【样例输出】

1

0

2

【数据范围】

对于30%的数据, n,q<=1000;

另有20%的数据,保证第城市2-n均可直接到达城市1;

另有10%的数据,保证城市i(1<=i<=n-1)可直接到达城市i+1;

对于100%的数据, n,q<=100000,li<=ri,任意两个城市的距离小于10^9。

【题解】

本题来自吉大附中wyf

对于30%的数据,暴力模拟

对于菊花图,分类讨论一下询问点是不是1号点,用rmq维护一段区间到1号点的最短距离。

一条链维护前缀和贪心。

对于100%的数据

1.分块!?

恩解决了。?能卡过、、

预处理每个点要走多远能到达某个块内的点,对于询问整块调用预处理答案,剩下暴力。

2.线段树

每一个线段树结点维护一棵区间内的标号的点形成的虚树,对于每次询问,拆分成logn段区间,然后分别询问。

将询问离线处理,不妨将询问点都插入区间虚树中,然后对每个线段树的结点一次树形dp来计算答案。

线段树结点中虚树总点数为(n+q)logn,加上构建虚树的复杂度,总复杂度(n+q)log^2n

分块(常数大的飞起)