当前位置：首页 > news >正文

HDU - 6393 Traffic Network in Numazu 树上倍增求lca+dfs序+线段树

news 来源：原创 2023/6/6 19:16:04

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6393

题意：n个点n条边的图，求两点间的最小距离

题解：如果是一个树的话，那么我们就可以倍增+dfs序，然后用线段树维护下就可以了这样是nlogn的复杂度，当然也可以剖分一下，这样就是nlognlogn的复杂度了，都是可以的，但这个是n条边，那么就会有一个环，那么两点间的距离就会存在两个的情况，因此我们先拆除环上的一条边(u-v)的来，剩下的n-1条就按照之前的方法求，那么假设求x到y的距离，那么还需要判断一下x - u - v - y 和 x - v - u - y。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
struct edge {int to, nex, d,id;
}e[N << 1];
struct EDGE {int x, y, z;
}E[N];
int n, m;
int head[N], len;
int vis[N];
ll dis[N];
int dp[N][22];
int dep[N];
int in[N], out[N];
int pid[N];
int tot;
void add(int x,int y,int z,int id){e[len].to=y;e[len].d=z;e[len].id=id;e[len].nex=head[x];head[x]=len++;
}
void init(){len=0;tot = 0;for(int i=0;i<=n;i++){head[i]=-1;vis[i]=0;for(int j=0;j<22;j++)dp[i][j]=0;}
}
int flagu,flagv,flagid;
void dfs1(int u,int fa){if(flagu!=-1)return;vis[u]=1;int to;for(int i=head[u];i!=-1;i=e[i].nex){to=e[i].to;if(to==fa)continue;if(vis[to]&&flagu==-1){flagu=u;flagv=to;flagid=e[i].id;return;}dfs1(to,u);}
}
void dfs2(int u,int fa){int to;dep[u] = dep[fa] + 1;in[u] = ++tot;pid[tot] = u;for(int i = head[u]; i != -1; i = e[i].nex) {to = e[i].to;if(to == fa) continue;if(e[i].id == flagid) continue;dis[to] = dis[u] + e[i].d;dp[to][0] = u;for(int j = 1; j < 22; j++)if(dp[to][j - 1])dp[to][j] = dp[dp[to][j - 1]][j - 1];elsebreak;dfs2(to, u);}out[u] = tot;
}
struct node {int l, r;ll val, laz;
}tree[N << 2];
void build(int l, int r, int cur) {tree[cur].l = l;tree[cur].r = r;tree[cur].laz = 0;tree[cur].val = 0;if(l == r) {tree[cur].val = dis[pid[l]];return;}int mid = (l + r) >> 1;build(l, mid, cur << 1);build(mid + 1, r, cur << 1 | 1);
}
void pushdown(int cur) {if(tree[cur].laz) {tree[cur << 1].laz += tree[cur].laz;tree[cur << 1].val += tree[cur].laz;tree[cur << 1 | 1].laz += tree[cur].laz;tree[cur << 1 | 1].val += tree[cur].laz;tree[cur].laz = 0;}
}
void update(int pl, int pr, int cur, ll val) {if(pl <= tree[cur].l && tree[cur].r <= pr) {tree[cur].laz += val;tree[cur].val += val;return;}pushdown(cur);if(pl <= tree[cur << 1].r) update(pl, pr, cur << 1, val);if(pr >= tree[cur << 1 | 1].l) update(pl, pr, cur << 1 | 1, val);
}
ll query(int pos, int cur) {if(tree[cur].l == tree[cur].r) {return tree[cur].val;}pushdown(cur);if(pos <= tree[cur << 1].r) return query(pos, cur << 1);else return query(pos, cur << 1 | 1);
}
int getlca(int x, int y) {if(dep[x] < dep[y]) swap(x, y);int cnt = dep[x] - dep[y];for(int i = 0; i < 22; i++) {if((cnt >> i) & 1)x = dp[x][i];}if(x == y) return x;for(int i = 21; i >= 0; i--) {if(dp[x][i] != dp[y][i]) {x = dp[x][i];y = dp[y][i];}}return dp[x][0];
}
int main() {int T;int x, y, z;int op;ll ans1, ans2, ans3;scanf("%d", &T);while(T--) {scanf("%d %d", &n, &m);init();for(int i = 1; i <= n; i++) {scanf("%d %d %d",&x, &y, &z);add(x,y,z,i);add(y,x,z,i);E[i].x = x;E[i].y = y;E[i].z = z;}flagu=-1;dfs1(1,0);dfs2(1,0);build(1, n, 1);while(m--) {scanf("%d %d %d", &op, &x, &z);if(op == 0) {if(x == flagid) {E[flagid].z = y;} else {if(dp[E[x].x][0] == E[x].y) {y = E[x].x;} else {y = E[x].y;}update(in[y], out[y], 1, z - E[x].z);E[x].z = z;}} else {dis[x] = query(in[x], 1);dis[z] = query(in[z], 1);dis[flagu] = query(in[flagu], 1);dis[flagv] = query(in[flagv], 1);ans1 = dis[x] + dis[z] - 2 * dis[getlca(x, z)];ans2 = dis[x] + dis[flagu] - 2 * dis[getlca(x, flagu)] + dis[z] + dis[flagv] - 2 * dis[getlca(z, flagv)] + E[flagid].z;ans3 = dis[x] + dis[flagv] - 2 * dis[getlca(x, flagv)] + dis[z] + dis[flagu] - 2 * dis[getlca(z, flagu)] + E[flagid].z;printf("%lld\n", min(ans1, min(ans2, ans3)));}}}return 0;
}

相关文章：