NO IMAGE

傳送門
悟: 樹上路徑相交問題一定和他們之間的LCA的最深的那一兩個有關係!!!

題目大意:

給定一棵n個點的樹,以及m條路徑,每次詢問第L條到第R條路徑的交集部分的長度(如果一條邊同時出現在2條路徑上,那麼它屬於路徑的交集)

思路: 首先我們考慮兩條路徑相交的情況, A – > B, C – > D, 很明顯這兩條相交路徑為LCA(A, C), LCA(A, D), LCA(B, C), LCA(B, D), 其中最深的兩個點之間的路徑, 所以路徑之間就具有合併性, 詢問又是問區間, 很明顯就要用線段樹, 每個葉子結點代表一條路徑, 然後pushup的時候就像上面所說的這樣做, 然後即可完成.

AC Code

const int maxn = 5e5   5;
int up[maxn][23];
int deep[maxn], dis[maxn];
int cnt, head[maxn];
int n, m, q;
struct node {
int to, next, w;
}e[maxn<<1];
void init() {
Fill(head,-1); Fill(dis,0);
Fill(up,0); Fill(deep,0);
cnt = 0;
}
void add(int u, int v, int w) {
e[cnt] = node{v, head[u], w};
head[u] = cnt  ;
}
void dfs(int u,int fa,int d) {
deep[u] = d   1;
for(int i = 1 ; i < 20 ; i   ) {
up[u][i] = up[up[u][i-1]][i-1];
}
for(int i = head[u] ; ~i ; i = e[i].next) {
int to = e[i].to;
if(to == fa) continue;
dis[to] = dis[u]   e[i].w;
up[to][0] = u;
dfs(to, u, d 1);
}
}
int LCA_BZ(int u,int v) {
int mx = 0;
if(deep[u] < deep[v]) swap(u,v);
int k = deep[u] - deep[v];
for(int i = 19 ; i >= 0 ; i --) {
if((1<<i) & k) {
u = up[u][i];
}
}
if(u == v) return u;
for(int i = 19 ; i >= 0 ; i --) {
if(up[u][i] != up[v][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
bool cmp(int x, int y) {
return deep[x] > deep[y];
}
pii Un(pii x, pii y) {
int a[5];
a[1] = LCA_BZ(x.fi, y.fi); a[2] = LCA_BZ(x.fi, y.se);
a[3] = LCA_BZ(x.se, y.fi); a[4] = LCA_BZ(x.se, y.se);
sort(a 1, a 5, cmp);
return {a[1], a[2]};
}
struct Tree {
int tl, tr;
pii path;
}tree[maxn<<2];
pii a[maxn];
void pushup(int i) {
tree[i].path = Un(tree[i<<1].path, tree[i<<1|1].path);
}
void build(int id, int l, int r) {
tree[id].tl = l; tree[id].tr = r;
if (l == r) {
tree[id].path = a[l];
return ;
}
int mid = (l   r) >> 1;
build(id<<1, l, mid); build(id<<1|1, mid 1, r);
pushup(id);
}
pii query(int id, int ql, int qr) {
int l = tree[id].tl, r = tree[id].tr;
if (ql <= l && r <= qr) return tree[id].path;
int mid = (l   r) >> 1;
if (qr <= mid) return query(id<<1, ql, qr);
else if (ql > mid) return query(id<<1|1, ql, qr);
else {
return Un(query(id<<1, ql, mid), query(id<<1|1, mid 1, qr));
}
}
void solve() {
scanf("%d",&n); init();
for(int i = 1 ; i < n ; i   ) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w); add(v, u, w);
}
dfs(1, -1, 0); scanf("%d", &m);
for (int i = 1 ; i <= m ; i   ) scanf("%d%d", &a[i].fi, &a[i].se);
build(1, 1, m);
scanf("%d", &q);
while(q--) {
int l, r;
scanf("%d%d", &l, &r);
pii t = query(1, l, r);
int res = dis[t.fi]   dis[t.se] - 2 * dis[LCA_BZ(t.fi, t.se)];
printf("%d\n", res);
}
}