P8805 [藍橋杯 2022 國 B] 機房

分析

是一道lca題目，可以直接套模板 + 前綴和處理點權

具體思路：

1.n臺電腦用n-1條網線相連，任意兩個節點之間有且僅有一條路徑（拆分成各自到公共祖先節點的路徑——lca）；

2.“延遲時間”：看成是節點點權（要求一條鏈上某個區間的值——前綴和）

——用sum[]存儲根節點到 i 節點的點權和

LCA

三種求法：

（1）樸素求法：

先將兩點位于同一深度，然后同時向上跳；一次查詢：O(n^2)

（2）倍增求法：

樸素求法的改進版（樸素是一步一步跳，倍增是用f[][]優化，每次向上都是以其父節點為目標）

（3）Tarjan（留一下，還沒學~）

倍增求法的步驟：

1.存圖/樹

2.dfs(int x,int father)更新f[][]（表示節點 i 的第2^j個祖先節點）、d[]（深度）

（1）更新d[x]和f[x][0]

（2）for(1~20)更新f[x][i]

（3）for(遍歷鄰接點)遞歸dfs()

3.lca

（1）先將兩點跳到同一深度（深度大的往上跳）

（2）若相等，則該點就是lca；若不相等，則從大到小，如果f[][]不等，則更新兩點，lca=f[x][0]

代碼?

#include<iostream>
#include<cstring>
using namespace std;const int N = 100010;
int head[N],d[N],f[N][30],a[N],sum[N],cnt,n,m;
struct edges{int to;int ne;
}e[N*2];//存兩條邊記得數組開成2倍//初始化別忘了（容易忘建議直接寫main中）
void init()
{memset(head,-1,sizeof head);
}
//鏈式前向星存邊
void addedge(int u,int v)
{e[cnt].to = v;e[cnt].ne = head[u];head[u] = cnt ++;
}
//dfs處理d[]、f[][]、sum[]
void dfs(int x,int father)
{d[x] = d[father] + 1;f[x][0] = father;sum[x] = sum[f[x][0]] + a[x];  //lca模板多了這一步~for(int i = 1;i <= 20;i ++){f[x][i] = f[f[x][i-1]][i-1];}for(int i = head[x];i != -1;i = e[i].ne){int j = e[i].to;if(j == father) continue; //加的是雙向邊，所以鄰接點有其父節點，遍歷時跳過dfs(j,x);	//遞歸遍歷}return ;
}
//lca找到最近公共祖先節點
int lca(int u,int v)
{if(d[u] < d[v]) swap(u,v);for(int i = 20;i >= 0;i --){if(d[f[u][i]] >= d[v]) u = f[u][i];}if(u == v){return u;}for(int i = 20;i >= 0;i --){if(f[u][i] != f[v][i]){u = f[u][i];v = f[v][i];}}return f[u][0];
}int main()
{init();scanf("%d %d",&n,&m);for(int i = 0;i < n - 1;i ++){int u,v;scanf("%d %d",&u,&v);a[u] ++,a[v] ++;addedge(u,v),addedge(v,u);}dfs(1,0);while(m --){int u,v;scanf("%d %d",&u,&v);int mid = lca(u,v);int ans = sum[u] + sum[v] - 2 * sum[mid] + a[mid];  //兩點之間的權值和printf("%d\n",ans);}return 0;
}