- 题目来源
描写叙述
今天，是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#include #include #include #define ll long long#define maxn 100005#define root 1#define nil 0using 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;}