Vijos1935不可思议的清晨题解
- 题目来源
描写叙述
今天，是2015年2月14日，星期六，情人节。
这真是一个不可思议的日子。今天早上。我打开窗户，太阳居然从西側升了起来。
我与木姑娘已经有2年半没有联系了。今天早上却被她的电话弄醒。她告诉我。她已经到了上海，希望能够和我以特殊的方式见面。
今天，SH市的交通情况异常有趣，非常多道路都被严令禁止通行。也许是由于太阳从西側升起来的缘故吧。
余下的交通网行程了一个树型结构，以n个路口为结点。第i个路口附近有p[i]处咖啡厅。
假设知道了我和木姑娘分别所处的位置，在选择余下某一个路口的某一处咖啡厅作为见面的场所，怎样呢？
哦。那或者距离我近，或者距离木姑娘近。
那么，究竟有多少咖啡厅距离我更近，又有多少咖啡厅距离木姑娘更近呢？（对于距离我和距离木姑娘一样近的咖啡厅，将被排除在这两类之外。）格式
输入格式
输入数据的第一行是一个整数n，表示路口的数目。
接下来的n-1行，每行三个整数u,v,w表示一条边从路口u到路口v。长度为w。接下来的一行n个数p1,p2,…,pn表示每一个路口的咖啡厅个数。
接下来的一行一个整数Q表示询问的数目。
接下来的Q行，每行两个整数x,y表示一组询问。当中我在x路口的位置。木姑娘在y路口的位置。输出格式
对于每组询问，输出一行两个整数分别表示距离x更近的咖啡厅总数。与距离y更近的咖啡厅总数。例子
例子输入
3
1 2 1
1 3 1
10 1 1
2
2 3
1 3
例子输出
1 1
11 1限制
对于30％的数据。n<=1000。
对于50％的数据。n<=20000。
对于100％的数据，n<=100000，Q<=50000，0<=w,p[i]<=1000000000。题解
这确实是一道不可思议的题目，在Vijos放出来以后，半年来通过率为0（事实上前辈们提交的程序全是0分）。我这个蒟蒻本来是抱着试一试玩一玩的心态，看看乱搞这个题会是什么结果。
可结果实在是太出乎意料了，我居然成了第一个AC此题的人。
先想一个可行的算法。
通过分析题目能够发现。这棵树能够以随意一个结点为根，就默觉得1吧。对于每一次询问x和y，都有一条唯一确定的路径x→y。这条路径把树分为三部分——离x更近的路径外的点、离y更近的路径外的点和路径上的点。
显然，离x更近的路径外的点上全部咖啡厅都离x更近。离y更近的路径外的点上全部咖啡厅都离y更近。以下分析路径上的点。由于我们人为确定了树根为1。所以x可能是y的祖先，y也可能是x的祖先，x与y也有可能互不为祖先。那路径x→y的形态就非常多了。不easy处理。
我们记t=lca(x,y)，即t为x与y的近期公共祖先，并用这个t把路径分为两部分——x→t和y→t，这样这两部分都是从叶子指向根的路径。处理起来就比較方便。从叶子到根，我们能够算出这条路径上到x与y距离最接近的一对点（或者算出了某个到x与y的距离同样的点），至少能够暴力枚举来算。
暂且称它为“转折点”吧。
我们记w(i,j)为从i到j的距离，那么有w(j,i)==w(i,j)。（貌似是废话）所谓转折点，要么是t，要么在x→t上，要么在y→t上，不可能跨越t（假设真有跨越t的转折点，那t一定是转折点）。以下分情况讨论。
先不考虑t==x或t==y的情况。假设t是转折点，那么w(x,t)==w(y,t)。记t的某一儿子结点是tmpx，且tmpx是x的祖先；同理记一个tmpy。那么t以及t的祖先以及t除了tmpx和tmpy的全部其它儿子中所含的咖啡厅对答案没有贡献，由于这些咖啡厅距离x和y相等。
离x更近的全部咖啡厅都在以tmpx为根的子树中。离y更近的全部咖啡厅都在以tmpy为根的子树中。想办法搞出来总数就可以。这个能够參照例子的第一个输出。
那假设t不是转折点又怎样呢？以转折点在x→t上为例。从x往t爬，利用w()函数（先别问w()怎么求），总能确定转折点。y→t上同理。离x近的咖啡厅总数是从离x近的转折点往x算的。离y近的咖啡厅总数是从离y近的转折点往y算的。这样就知道答案怎么求了。
把t==x或t==y的情况代入上述分析。发现答案的求法基本同样，仅仅是tmpx和tmpy不是转折点的儿子，而是从转折点往x或y上“多走”一步的结点。
我们记dist(x)为从x到根的距离，dep(x)为x结点的深度，s(x)为以1为根后的整棵树中以x为根的子树含有咖啡厅的总数，它们都能在同一遍从根開始的dfs中用O(n)的时间里确定。
那么w(i,j)=dist(i)+dist(j)−2∗dist(lca(i,j))，能够在O(1)的时间里确定。
如今谈一下乱搞的基础：这个题没有涉及到改动操作。
“引理”：树上乱搞用倍增。
lca倍增求出，O(nlogn)。
全部“往上爬”的操作，用倍增。O(logn)；
再暴力一点，把全部“多走一步”变成从孙子辈“找祖先”，继续倍增，O(logn)。
别看题目看起来挺复杂的。事实上是非常多倍增的小题组合起来了。一部分一部分耐心写下去就能够了。看数据范围是要开longlong的。输出时纠结了一会儿”%lld”和”%I64d”，于是直接iostream了。
时限3s，总时间复杂度O((n+q)logn)。最慢的2s多一点，开读写优化可能能杀进1s。
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define ll long long
#define maxn 100005
#define root 1
#define nil 0
using namespace std;
int n, q, fa[maxn][20], dep[maxn];
ll d[maxn], val[maxn], s[maxn];
ll u[maxn << 1], v[maxn << 1], w[maxn << 1], nxt[maxn << 1], pnt[maxn], e;
bool vis[maxn];
void add(ll a, ll b, ll c)
{
u[++e] = a; v[e] = b; w[e] = c;
nxt[e] = pnt[a]; pnt[a] = e;
u[++e] = b; v[e] = a; w[e] = c;
nxt[e] = pnt[b]; pnt[b] = e;
}
void dfs(int rot)
{
vis[rot] = true;
s[rot] = val[rot];
for(int j = pnt[rot]; j != nil; j = nxt[j])
{
if(!vis[v[j]])
{
fa[v[j]][0] = rot;
dep[v[j]] = dep[rot] + 1;
d[v[j]] = d[rot] + w[j];
dfs(v[j]);
s[rot] += s[v[j]];
}
}
}
void init()
{
ll a, b, c;
cin >> n;
for(int i = 1; i < n; ++i)
{
cin >> a >> b >> c;
add(a, b, c);
}
for(int i = 1; i <= n; ++i)
{
cin >> val[i];
}
memset(vis, 0, sizeof(vis));
dep[root] = 1;
dfs(root);
for(int j = 1; j < 20; ++j) for(int i = 1; i <= n; ++i)
{
fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
cin >> q;
}
int getlca(int x, int y)
{
if(dep[x] < dep[y]) swap(x, y);
for(int j = 19; j >= 0; --j)
{
if(dep[fa[x][j]] >= dep[y]) x = fa[x][j];
}
if(x == y) return x;
for(int j = 19; j >= 0; --j)
{
if(fa[x][j] != fa[y][j])
{
x = fa[x][j];
y = fa[y][j];
}
}
return fa[x][0];
}
void work()
{
int x, y, t;
ll ansx, ansy;
while(q--)
{
cin >> x >> y;
if(x == y)
{
cout << "0 0" << endl;
continue;
}
t = getlca(x, y);
if(d[x] - d[t] == d[y] - d[t])
{
int tmp = x;
for(int j = 19; j >= 0; --j)
{
if(dep[fa[tmp][j]] > dep[t]) tmp = fa[tmp][j];
}
ansx = s[tmp];
tmp = y;
for(int j = 19; j >= 0; --j)
{
if(dep[fa[tmp][j]] > dep[t]) tmp = fa[tmp][j];
}
ansy = s[tmp];
cout << ansx << " " << ansy << endl;
}
else if(d[x] - d[t] > d[y] - d[t])
{
int tmpx = x, tmpy, tmp;
for(int j = 19; j >= 0; --j)
{
if((dep[fa[tmpx][j]] > dep[t]) && (d[fa[tmpx][j]] + d[y] - (d[t] << 1) > d[x] - d[fa[tmpx][j]]))
{
tmpx = fa[tmpx][j];
}
}
ansx = s[tmpx];
tmpy = fa[tmpx][0];
for(int j = 19; j >= 0; --j)
{
if((dep[fa[tmpy][j]] > dep[t]) && (d[tmpy] == d[tmpx]))
{
tmpy = fa[tmpy][j];
}
}
tmp = tmpx;
for(int j = 19; j >= 0; --j)
{
if(dep[fa[tmp][j]] > dep[tmpy]) tmp = fa[tmp][j];
}
ansy = s[root] - s[tmp];
cout << ansx << " " << ansy << endl;
}
else
{
int tmpx, tmpy = y, tmp;
for(int j = 19; j >= 0; --j)
{
if((dep[fa[tmpy][j]] > dep[t]) && (d[fa[tmpy][j]] + d[x] - (d[t] << 1) > d[y] - d[fa[tmpy][j]]))
{
tmpy = fa[tmpy][j];
}
}
ansy = s[tmpy];
tmpx = fa[tmpy][0];
for(int j = 19; j >= 0; --j)
{
if((dep[fa[tmpx][j]] > dep[t]) && (d[tmpx] == d[tmpy]))
{
tmpx = fa[tmpx][j];
}
}
tmp = tmpy;
for(int j = 19; j >= 0; --j)
{
if(dep[fa[tmp][j]] > dep[tmpx]) tmp = fa[tmp][j];
}
ansx = s[root] - s[tmp];
cout << ansx << " " << ansy << endl;
}
}
}
int main()
{
init();
work();
return 0;
}最新文章
- jQuery 邮箱下拉列表自动补全
- 转：android异步任务设计思详解(AsyncTask)
- 【leetcode】Decode Ways(medium)
- 百度地图api根据定位获取附近商家（只获取屏幕内）
- 【poj1962】 Corporative Network
- Codeforces Round #373 (Div. 2) A B C 水 贪心 模拟(四舍五入进位)
- 检查dns服务器是否可用
- [ Database ] [ Sybase ] [ SQLServer ] sybase 與SQL Server的界接方式
- Bash关闭输出（关闭正确、错误输出）
- HBuilder+移动APP开发实例
- vs2010中出现:程序管理器匹配不正确错误
- Android UI高级交互设计Demo
- hosts文件不显示
- One day one cf,Keep Wa away from me.
- 10分钟学会JAVA注解（annotation）
- 【译】图解Transformer
- centos7下安装docker（16.1docker跨主机存储--Rex-Ray）
- linux--- python3环境部署篇
- perl二维数组
- python 路径和文件的遍历