| Time Limit: 4000MS | Memory Limit: 65536K | |
| Total Submissions: 11419 | Accepted: 3140 |
Description
Input
Output
Sample Input
3 3 1 1 2 1 2 3 2 0 2 1 2 3 0 3
Sample Output
1 3
题目链接：POJ 2763
给定一棵树，两种操作，一种是询问当前点到v点的最短距离，并且输出答案之后当前点就变成v点了；第二种是把某一条边的长度变为w。
先考虑只有询问的情况下怎么做，显然是LCA裸题，设dis[u]代表u点到根节点的距离，则有：$dis(u, v) = dis[u]+dis[v]-2*dis[LCA(u,v)]$，然后考虑第二种操作，可以发现当你改变一条边的长度（权值）的时候，会对这条边下的整颗子树造成影响，比如u——v的一条边，且u比v更靠近根节点的话，那么造成的影响是v所在整颗子树的影响，即子树是深度较深的点所连接的。由于是整颗子树，明显可以用DFS序来转换后用树状数组或者线段树来维护这个DFS序列即dis数组，操作就是区间更新，单点查询——改变边长度的时候显然整个子树序列区间长度均改变了$w‘-w$。好像这题一般写法是树链剖分，蒟蒻我不会……就用树状数组好了，树状数组怎么区间更新？左端点处+val，右端点+1处-val即可。
ZZ地WA了一下午发现是把D数组当作深度数组来用了……
代码：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <sstream>
#include <numeric>
#include <cstring>
#include <bitset>
#include <string>
#include <deque>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,sum) memset(arr,sum,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
struct edge
{
int to, nxt, d;
edge() {}
edge(int _to, int _nxt, int _d): to(_to), nxt(_nxt), d(_d) {}
};
edge E[N << 1];
int head[N], tot;
int ver[N << 1], D[N << 1], F[N], sz, dp[N << 1][19];
int W[N], A[N], B[N];
int L[N], R[N], T[N], ts;
bitset<N>vis;
void init()
{
CLR(head, -1);
tot = 0;
sz = 0;
ts = 0;
CLR(T, 0);
vis.reset();
}
void update(int k, int v)
{
while (k < N)
{
T[k] += v;
k += (k & -k);
}
}
int query(int k)
{
int ret = 0;
while (k)
{
ret += T[k];
k -= (k & -k);
}
return ret;
}
inline void add(int s, int t, int d)
{
E[tot] = edge(t, head[s], d);
head[s] = tot++;
}
void dfs(int u, int d, int sumdis)
{
ver[++sz] = u;
D[sz] = d;
F[u] = sz;
L[u] = ++ts;
update(L[u], sumdis);
update(L[u] + 1, -sumdis);
vis[u] = 1;
for (int i = head[u]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if (!vis[v])
{
dfs(v, d + 1, sumdis + E[i].d);
ver[++sz] = u;
D[sz] = d;
}
}
R[u] = ts;
}
void RMQinit(int l, int r)
{
int i, j;
for (i = l; i <= r; ++i)
dp[i][0] = i;
for (j = 1; l + (1 << j) - 1 <= r; ++j)
{
for (i = l; i + (1 << j) - 1 <= r; ++i)
{
int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1];
dp[i][j] = D[a] < D[b] ? a : b;
}
}
}
int LCA(int u, int v)
{
int l = F[u], r = F[v];
if (l > r)
swap(l, r);
int len = r - l + 1;
int k = 0;
while (1 << (k + 1) <= len)
++k;
int a = dp[l][k], b = dp[r - (1 << k) + 1][k];
return D[a] < D[b] ? ver[a] : ver[b];
}
int main(void)
{
int n, q, s, i, a, b, w;
while (~scanf("%d%d%d", &n, &q, &s))
{
init();
for (i = 1; i <= n - 1; ++i)
{
scanf("%d%d%d", &a, &b, &w);
A[i] = a;
B[i] = b;
W[i] = w;
add(a, b, w);
add(b, a, w);
}
dfs(s, 1, 0);
RMQinit(1, sz);
while (q--)
{
int ops;
scanf("%d", &ops);
if (ops == 0)
{
int v;
scanf("%d", &v);
printf("%d\n", query(L[s]) + query(L[v]) - 2 * query(L[LCA(s, v)]));
s = v;
}
else
{
int k, neww;
scanf("%d%d", &k, &neww);
int u = A[k], v = B[k];
if (L[u] > L[v])
swap(u, v);
update(L[v], neww - W[k]);
update(R[v] + 1, -(neww - W[k]));
W[k] = neww;
}
}
}
return 0;
}
POJ 2763 Housewife Wind（DFS序+LCA+树状数组）
原文：http://www.cnblogs.com/Blackops/p/7142323.html