A - How far away ？
HDU - 2586 题意：给出一棵树，树上的边有权值，查询两个点之间的最短权值和
LCA倍增
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 4e4 + 5; const int mod = 998244353; int cnt,DEG = 30; int vis[maxn],head[maxn],dep[maxn],fa[maxn][30],dis[maxn]; struct EDGE { int next,to,v; }edge[maxn * 2]; void addedge(int x,int y,int z) { edge[++cnt].to = y; edge[cnt].v = z; edge[cnt].next = head[x]; head[x] = cnt; } void init() { cnt = 0; memset(vis,0,sizeof vis); memset(head,-1,sizeof head); memset(dep,0,sizeof dep); memset(dis,0,sizeof dis); } void bfs(int root) { queue<int>que; dep[root] = 0; fa[root][0] = root; que.push(root); while(!que.empty()) { int tmp = que.front(); que.pop(); for(int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; for(int i = head[tmp]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == fa[tmp][0]) continue; dep[v] = dep[tmp] + 1; dis[v] = dis[tmp] + edge[i].v; fa[v][0] = tmp; que.push(v); } } } int LCA(int u,int v) { if(dep[u] > dep[v]) swap(u,v); int hu = dep[u],hv = dep[v],tu = u,tv = v; for(int det = hv - hu, i = 0; det; det >>= 1, i++) if(det & 1) tv = fa[tv][i]; if(tu == tv) return tu; for(int i = DEG - 1; i >= 0; i--) { if(fa[tu][i] == fa[tv][i]) continue; tu = fa[tu][i]; tv = fa[tv][i]; } return fa[tu][0]; } int main() { int t; scanf("%d",&t); while (t -- ) { init(); int n, m; scanf("%d %d",&n,&m); for(int i = 1; i < n; i++) { int u,v,k; scanf("%d %d %d",&u,&v,&k); vis[v] = 1; addedge(u,v,k); addedge(v,u,k); } int root; for(int i = 1; i <= n; i++ ) { if(vis[i] == 0) { root = i; break; } } bfs(root); for(int i = 1; i <= m; i++) { int a,b; scanf("%d %d",&a,&b); int ans = dis[a] + dis[b] - 2 * dis[LCA(a,b)]; printf("%d ",ans); } } }
B - Distance Queries
POJ - 1986LCA倍增模版，加注释！！
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 4e4 + 5; const int mod = 998244353; int cnt,DEG = 30; int vis[maxn],head[maxn],dep[maxn],fa[maxn][30],dis[maxn]; //dep深度数组 fa[i][j]表示结点 i 的第2 ^ j个祖先 //dis[i] root到任意的一个i结点的距离 struct EDGE { int next,to,v; }edge[maxn * 2]; void addedge(int x,int y,int z) { edge[++cnt].to = y; edge[cnt].v = z; edge[cnt].next = head[x]; head[x] = cnt; } void init() { cnt = 0; memset(vis,0,sizeof vis); memset(head,-1,sizeof head); memset(dep,0,sizeof dep); memset(dis,0,sizeof dis); memset(fa,0,sizeof fa); } void bfs(int root) { queue<int>que; dep[root] = 0; //根节点的深度为0 fa[root][0] = root; que.push(root); while(!que.empty()) { int tmp = que.front(); que.pop(); for(int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; //tmp这个点的2 ^ i的祖先就是 tmp的 2 ^ (i - 1)的祖先这个点的 2 ^ (i - 1)的祖先 for(int i = head[tmp]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == fa[tmp][0]) continue; dep[v] = dep[tmp] + 1; dis[v] = dis[tmp] + edge[i].v; //dis距离数组的更新 fa[v][0] = tmp; que.push(v); } } } int LCA(int u,int v) { if(dep[u] > dep[v]) swap(u,v); //使得v的深度比较大 int hu = dep[u],hv = dep[v],tu = u,tv = v; for(int det = hv - hu, i = 0; det; det >>= 1, i++) if(det & 1) tv = fa[tv][i]; if(tu == tv) return tu; for(int i = DEG - 1; i >= 0; i--) { if(fa[tu][i] == fa[tv][i]) continue; tu = fa[tu][i]; tv = fa[tv][i]; } return fa[tu][0]; } int main() { init(); int n, m; while (~scanf("%d %d", &n, &m)) { for (int i = 1; i <= m; i++) { int u, v, k; char s[10]; scanf("%d %d %d %s", &u, &v, &k, s); vis[v] = 1; addedge(u, v, k); addedge(v, u, k); } int root; for (int i = 1; i <= n; i++) { if (vis[i] == 0) { root = i; break; } } bfs(root); int k; scanf("%d", &k); for (int i = 1; i <= k; i++) { int a, b; scanf("%d %d", &a, &b); int ans = dis[a] + dis[b] - 2 * dis[LCA(a, b)]; printf("%d ", ans); } } }
C - Connections between cities
HDU - 2874
森林求LCA
倍增 + 并查集
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 1e5 + 5; const int mod = 998244353; struct Edge { int to,next,v; }edge[maxn * 2]; const int DEG = 30; int head[maxn],dep[maxn],fa[maxn][DEG],dis[maxn]; bool vis[maxn]; int pre[maxn]; int tot; void init() { tot = 0; memset(dis,0,sizeof dis); memset(head,-1,sizeof head); memset(vis,false,sizeof vis); memset(dep,0,sizeof dep); } int find(int x) { if(pre[x] != x) return pre[x] = find(pre[x]); return x; } void combine(int x,int y) { int fx = find(x); int fy = find(y); if(fx != fy) { pre[fx] = fy; } } void addedge(int u,int v,int z) { edge[tot].to = v; edge[tot].next = head[u]; edge[tot].v = z; head[u] = tot++; } void BFS(int root) { queue<int>que; dep[root] = 0; fa[root][0] = root; que.push(root); while(!que.empty()) { int tmp = que.front(); que.pop(); for(int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; for(int i = head[tmp]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == fa[tmp][0]) continue; dep[v] = dep[tmp] + 1; dis[v] = dis[tmp] + edge[i].v; fa[v][0] = tmp; que.push(v); } } } int LCA(int u,int v) { if(dep[u] > dep[v]) swap(u,v); int hu = dep[u],hv = dep[v]; int tu = u,tv = v; for(int det = hv - hu,i = 0; det ; det >>= 1, i++) if(det & 1) tv = fa[tv][i]; if(tu == tv) return tu; for(int i = DEG - 1; i >= 0; i--) { if(fa[tu][i] == fa[tv][i]) continue; tu = fa[tu][i]; tv = fa[tv][i]; } return fa[tu][0]; } int main() { int n, m, k; while(~scanf("%d %d %d",&n,&m,&k)) { init(); for (int i = 1; i <= n; i++) pre[i] = i; for (int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); addedge(a, b, c); addedge(b, a, c); combine(a, b); vis[b] = true; } int root; for (int i = 1; i <= n; i++) { if (vis[i] == false) { root = i; break; } } for (int i = 1; i <= n; i++) if (pre[i] == i) BFS(i); while (k--) { int a, b; scanf("%d %d", &a, &b); if (find(a) != find(b)) puts("Not connected"); else { int ans = dis[a] + dis[b] - 2 * dis[LCA(a, b)]; printf("%d ", ans); } } } }
D - Design the city
ZOJ - 3195
题意：求树上三点间的最短距离。
思路：ans=(dis(a,b)+dis(a,c)+dis(b,c))/2
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 5e4 + 5; const int mod = 998244353; int cnt,DEG = 30; int vis[maxn],head[maxn],dep[maxn],fa[maxn][30],dis[maxn]; struct EDGE { int next,to,v; }edge[maxn * 2]; void addedge(int x,int y,int z) { edge[++cnt].to = y; edge[cnt].v = z; edge[cnt].next = head[x]; head[x] = cnt; } void init() { cnt = 0; memset(vis,0,sizeof vis); memset(head,-1,sizeof head); memset(dep,0,sizeof dep); memset(dis,0,sizeof dis); } void bfs(int root) { queue<int>que; dep[root] = 0; fa[root][0] = root; que.push(root); while(!que.empty()) { int tmp = que.front(); que.pop(); for(int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; for(int i = head[tmp]; i != -1; i = edge[i].next) { int v = edge[i].to; if(v == fa[tmp][0]) continue; dep[v] = dep[tmp] + 1; dis[v] = dis[tmp] + edge[i].v; fa[v][0] = tmp; que.push(v); } } } int LCA(int u,int v) { if(dep[u] > dep[v]) swap(u,v); int hu = dep[u],hv = dep[v],tu = u,tv = v; for(int det = hv - hu, i = 0; det; det >>= 1, i++) if(det & 1) tv = fa[tv][i]; if(tu == tv) return tu; for(int i = DEG - 1; i >= 0; i--) { if(fa[tu][i] == fa[tv][i]) continue; tu = fa[tu][i]; tv = fa[tv][i]; } return fa[tu][0]; } int main() { int n, m; int ca = 0; while (~scanf("%d", &n)) { init(); if(ca > 0)printf(" "); ca++; for (int i = 1; i < n; i++) { int u, v, k; scanf("%d %d %d", &u, &v, &k); vis[v] = 1; addedge(u, v, k); addedge(v, u, k); } int root; for (int i = 0; i < n; i++) { if (vis[i] == 0) { root = i; break; } } scanf("%d",&m); bfs(root); for (int i = 1; i <= m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); int ans1 = dis[a] + dis[b] - 2 * dis[LCA(a, b)]; int ans2 = dis[a] + dis[c] - 2 * dis[LCA(a,c)]; int ans3 = dis[b] + dis[c] - 2 * dis[LCA(b,c)]; printf("%d ", (ans1 + ans2 + ans3) / 2); } } }
E - Network
HDU - 3078
题意：问你u，v最短路上所有节点权值的第k大
思路：就是u->lca(u,v)和v->lca（u，v）的所有节点权值放入数组，sort一下，输出第k大就行（这也太暴力了）
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 8e4 + 5; const int mod = 998244353; int cnt,DEG = 30; int vis[maxn],head[maxn],dep[maxn],fa[maxn][30],dis[maxn]; int w[maxn],path[maxn]; struct EDGE { int next,to; }edge[maxn * 2]; void addedge(int x,int y) { edge[++cnt].to = y; edge[cnt].next = head[x]; head[x] = cnt; } void init() { cnt = 0; memset(vis, 0, sizeof vis); memset(head, -1, sizeof head); memset(dep, 0, sizeof dep); memset(dis, 0, sizeof dis); memset(path, 0, sizeof path); } void bfs(int root) { queue<int> que; dep[root] = 0; fa[root][0] = root; que.push(root); while (!que.empty()) { int tmp = que.front(); que.pop(); for (int i = 1; i < DEG; i++) fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; for (int i = head[tmp]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == fa[tmp][0]) continue; dep[v] = dep[tmp] + 1; fa[v][0] = tmp; que.push(v); } } } int LCA(int u,int v) { if (dep[u] > dep[v]) swap(u, v); int hu = dep[u], hv = dep[v], tu = u, tv = v; for (int det = hv - hu, i = 0; det; det >>= 1, i++) if (det & 1) tv = fa[tv][i]; if (tu == tv) return tu; for (int i = DEG - 1; i >= 0; i--) { if (fa[tu][i] == fa[tv][i]) continue; tu = fa[tu][i]; tv = fa[tv][i]; } return fa[tu][0]; } bool cmp(int h1,int h2) { return h1 > h2; } int main() { int n, m; while (~scanf("%d %d", &n, &m)) { init(); for(int i = 1; i <= n; i++) scanf("%d", &w[i]); for (int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); vis[v] = 1; addedge(u, v); addedge(v, u); } int root; for (int i = 1; i <= n; i++) { if (vis[i] == 0) { root = i; break; } } bfs(root); for (int i = 1; i <= m; i++) { int k,a, b; scanf("%d %d %d", &k, &a, &b); if(k == 0) w[a] = b; else { int lca = LCA(a,b); int num = 0; for(int i = a; i != lca; i = fa[i][0]) path[++num] = w[i]; for(int i = b; i != lca; i = fa[i][0]) path[++num] = w[i]; path[++num] = w[lca]; if(num < k) { printf("invalid request! "); } else { sort(path + 1,path + 1 + num,cmp); printf("%d ",path[k]); } } } } }
K - Nearest Common Ancestors
POJ - 1330
ST表求LCA
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<stack> #include<cstdlib> #include<queue> #include<set> #include<string.h> #include<vector> #include<deque> #include<map> using namespace std; #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define eps 1e-4 #define bug printf("********* ") #define debug(x) cout<<#x"=["<<x<<"]" <<endl typedef long long LL; typedef long long ll; const int maxn = 1e4 + 5; const int mod = 998244353; int rmq[2 * maxn]; // 欧拉序列对应的深度序列 struct ST { int mm[2 * maxn]; int dp[2 * maxn][20]; void init(int n) { mm[0] = -1; for (int i = 1; i <= n; i++) { mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1]; dp[i][0] = i; } for (int j = 1; j <= mm[n]; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) dp[i][j] = rmq[dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][ j - 1]; } int query(int a, int b) { if (a > b) swap(a, b); int k = mm[b - a + 1]; return rmq[dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ? dp[a][k] : dp[b - (1 << k) + 1][k]; } }st; struct Edge { int to, next; }edge[maxn * 2]; int tot,head[maxn * 2]; int F[maxn * 2]; //欧拉序列 即dfs遍历的顺序 int P[maxn]; //表示点i在F中第一次出现的位置 int cnt; void init() { tot = 0; memset(head, -1, sizeof head); } void addedge(int u,int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } void dfs(int u,int pre,int dep) { F[++cnt] = u; rmq[cnt] = dep; P[u] = cnt; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (v == pre) continue; dfs(v, u, dep + 1); F[++cnt] = u; rmq[cnt] = dep; } } void LCA_init(int root,int node_num) { cnt = 0; dfs(root, root, 0); st.init(2 * node_num - 1); } int query_lca(int u,int v) { return F[st.query(P[u], P[v])]; } bool flag[maxn]; int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); init(); memset(flag, 0, sizeof flag); int u, v; for (int i = 1; i < n; i++) { scanf("%d %d", &u, &v); addedge(u, v); addedge(v, u); flag[v] = true; } int root; for (int i = 1; i <= n; i++) if (!flag[i]) { root = i; break; } LCA_init(root, n); scanf("%d %d", &u, &v); printf("%d ", query_lca(u, v)); } }