将边权->点权，只需要在dfs的时候求出两个点的深度，把边权下方到深度更深的节点上即可。
但是转化完之后，最后query_path的时候要注意，是求的son[u]和v之间的信息（因为点u保存的是u点到他的father节点之间的那条边，不应该算在u->v内）
Housewife Wind
tips：边权转化为点权，然后单点修改线段树，线段树维护区间和信息。
一点需要注意：如果query_path最后的u == v，就要直接break而不能算了。因为边权转化为点权后算son[u]和v的信息会出错。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
const int N = 200010;
int n,s,q,idx;
int fa[N],son[N],id[N],nw[N],sz[N],top[N],dep[N],cnt; //树链剖分
int w[N],ne[N],e[N],h[N],ww[N];
struct node{
int l, r, w;
}mp[N];
//线段树维护区间和
struct tr{
int l, r, sum;
}tr[N << 2];
void pushup(int u){ tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;}
void build(int u, int l, int r){
tr[u] = {l, r, nw[l]};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int x, int v){
if(tr[u].l == tr[u].r && tr[u].l == x){
tr[u].sum = v;
return ;
}else{
int mid = tr[u].l + tr[u].r >> 1;
if(x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
pushup(u);
}
}
int query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if(l <= mid) res += query(u << 1, l, r);
if(r > mid) res += query(u << 1 | 1, l, r);
return res;
}
//树链剖分
void dfs1(int u, int father, int depth){
sz[u] = 1, fa[u] = father, dep[u] = depth;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == father) continue ;
dfs1(j, u, depth + 1);
sz[u] += sz[j];
w[j] = ww[i]; //边权——>点权
if(sz[son[u]] < sz[j]) son[u] = j;
}
}
void dfs2(int u, int t){
id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
if(!son[u]) return ;
dfs2(son[u], t);
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa[u] || j == son[u]) continue ;
dfs2(j, j);
}
}
int query_path(int u, int v){
int res = 0;
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
res += query(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if(u == v) return res; //这里非常重要！！！！
if(dep[u] < dep[v]) swap(u, v);
res += query(1, id[son[v]], id[u]);
return res;
}
void add(int a, int b, int c){ e[idx] = b, ww[idx] = c, ne[idx] = h[a], h[a] = idx ++;}
int main(){
cin >> n >> q >> s;
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; ++ i){
int a, b, c;
scanf("%d%d%d",&a,&b,&c);
mp[i] = {a, b, c};
add(a, b, c), add(b, a, c);
}
dfs1(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
while(q --){
int op, x, v;
scanf("%d%d",&op,&x);
if(op == 0) printf("%d\n", query_path(s, x)), s = x;
else{
scanf("%d",&v);
int a = mp[x].l, b = mp[x].r;
if(dep[a] < dep[b]) swap(a, b);
modify(1, id[a], v);
}
}
return 0;
}I Imperial roads
题意：多组询问，每组询问固定一条边，求此时的mst的权值。
思路：先求出原图的mst，并建图（是原图的最小生成树）。然后每次询问的边如果在mst中，就直接输出mst的值，否则，在新图上求这条边连接的点之间的最长一条路径，把他去掉再加上新边的值即可。（加上一条新边之后会生成一个环，然后去掉原先这个环中最大的一条边即可）。
树链剖分后用线段树维护区间最大值（两点之间路径的权值最大的边）。
还是注意最后son[u]和v的问题。
#include<bits/stdc++.h>
#define PII pair<int, int>
#define ll long long
using namespace std;
const int N = 200010;
int n,m,q;
int f[N],ne[N],e[N],w[N],ww[N],idx,h[N]; // 建新图， ww是边权，w是点权
struct node{ // mst
int s, e, w;
}mp[N];
bool cmp(node n1, node n2){return n1.w < n2.w;}
int id[N],top[N],fa[N],sz[N],dep[N],son[N],nw[N],cnt; //树链剖分
ll ans; //mst的权值
map<PII, int> rec; //记录所有边
map<PII, bool> mst; //记录在mst中的边
struct tr{
int l, r, maxx;
}tr[N << 2];
void add(int a, int b, int c){ e[idx] = b, ww[idx] = c, ne[idx] = h[a], h[a] = idx ++;}
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]);}
int unite(int x, int y){
int r1 = find(x), r2 = find(y);
if(r1 == r2) return false;
f[r2] = r1; return true;
}
void kruskal(){
int num = 0;
for(int i = 1; i <= m; ++ i){
if(unite(mp[i].s, mp[i].e)){
ans += mp[i].w;
add(mp[i].s, mp[i].e, mp[i].w); add(mp[i].e, mp[i].s, mp[i].w); //建新图
mst[{mp[i].s, mp[i].e}] = true;
num ++;
}
if(num == n - 1) break;
}
}
void init(){
for(int i = 1; i <= n; ++ i) f[i] = i;
memset(h, -1, sizeof h);
}
// 线段树函数
void pushup(int u){ tr[u].maxx = max(tr[u << 1].maxx, tr[u << 1 | 1].maxx);}
void build(int u, int l, int r){
tr[u] = {l, r, nw[l]};
if(l == r) return;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
ll query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].maxx;
int mid = tr[u].l + tr[u].r >> 1;
ll res = 0;
if(l <= mid) res = max(res, query(u << 1, l, r));
if(r > mid) res = max(res, query(u << 1 | 1, l, r));
return res;
}
// 树链剖分函数
void dfs1(int u, int father, int depth){ //求重儿子
sz[u] = 1, fa[u] = father, dep[u] = depth;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == father) continue ;
dfs1(j, u, depth + 1);
if(dep[u] < dep[j]) w[j] = ww[i]; //点权->边权
else w[u] = ww[i];
sz[u] += sz[j];
if(sz[son[u]] < sz[j]) son[u] = j;
}
}
void dfs2(int u, int t){ //划分轻重链
id[u] = ++ cnt, top[u] = t, nw[cnt] = w[u];
if(!son[u]) return ;
dfs2(son[u], t);
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == fa[u] || j == son[u]) continue ;
dfs2(j, j);
}
}
ll query_path(int u, int v){
ll res = 0;
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
res = max(res, query(1, id[top[u]], id[u]));
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
res = max(res, query(1, id[son[v]], id[u])); //!!!!!
return res;
}
int main(){
cin >> n >> m;
init();
for(int i = 1; i <= m; ++ i) scanf("%d%d%d",&mp[i].s,&mp[i].e,&mp[i].w), rec[{mp[i].s, mp[i].e}] = mp[i].w;
sort(mp + 1, mp + 1 + m, cmp);
kruskal();
dfs1(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
cin >> q;
while(q --){
int a, b;
scanf("%d%d",&a,&b);
if(mst.count({a, b}) || mst.count({b, a})) printf("%d\n", ans);
else{
ll tmp = query_path(a, b);
int z = rec.count({a, b}) ? rec[{a, b}] : rec[{b, a}];
printf("%lld\n", ans + z - tmp);
}
}
return 0;
}
P3038 [USACO11DEC]Grass Planting G
题意： 给出一棵n个节点的树，有m个操作，操作为将一条路径上的边权加一或询问某条边的权值。
直接点权转边权即可。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010, M = 2 * N;
int n,m,e[M],h[N],w[N],ne[M],idx;
int cnt,top[N],sz[N],fa[N],nw[N],id[N],son[N],dep[N]; //树链剖分
struct node{
int l, r, sum, add;
}tr[N << 2];
void add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++;}
//线段树
void pushup(int u){ tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;}
void pushdown(int u){
if(tr[u].add){
tr[u << 1].add += tr[u].add, tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add;
tr[u << 1 | 1].add += tr[u].add, tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;
tr[u].add = 0;
}
}
void build(int u, int l, int r){
tr[u] = {l, r, 0, 0};
if(l == r) return ;
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int w){
if(tr[u].l >= l && tr[u].r <= r){
tr[u].add += w;
tr[u].sum += (tr[u].r - tr[u].l + 1) * w;
}else{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, w);
if(r > mid) modify(u << 1 | 1, l, r, w);
pushup(u);
}
}
int query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1, res = 0;
if(l <= mid) res += query(u << 1, l, r);
if(r > mid) res += query(u << 1 | 1, l, r);
return res;
}
//树链剖分
void dfs(int u, int father, int depth){
sz[u] = 1, fa[u] = father, dep[u] = depth;
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == father) continue ;
dfs(j, u, depth + 1);
sz[u] += sz[j];
if(sz[son[u]] < sz[j]) son[u] = j;
}
}
void dfs2(int u, int t){
id[u] = ++ cnt, nw[cnt] = w[u], top[u] = t;
if(!son[u]) return ;
dfs2(son[u], t);
for(int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if(j == son[u] || j == fa[u]) continue ;
dfs2(j, j);
}
}
void update_path(int u, int v, int w){
while(id[top[u]] != id[top[v]]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
modify(1, id[top[u]], id[u], w);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
modify(1, id[son[v]], id[u], w);
}
int query_path(int u, int v){
int res = 0;
while(id[top[u]] != id[top[v]]){
if(dep[top[u]] < dep[top[v]]) swap(u, v);
res += query(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if(dep[u] < dep[v]) swap(u, v);
res += query(1, id[son[v]], id[u]);
return res;
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 1; i <= n - 1; ++ i){
int a, b;
scanf("%d%d",&a,&b);
add(a, b), add(b, a);
}
dfs(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
while(m --){
char opt; int x, y;
scanf(" %c%d%d",&opt,&x,&y);
if(opt == 'P') update_path(x, y, 1);
else printf("%d\n", query_path(x, y));
}
return 0;
}
京公网安备 11010502036488号