題目鏈接：點擊查看

題目大意：給出一棵無根樹，每條邊都有權值，接下來有數次操作，每次操作分為兩種類型：

DIST x y：求出點x到點y的唯一路徑上的權值和

KTH x y k：求出點x到點y的唯一路徑上第k個點

題目分析：因為是無根樹，所以我們隨便找個節點當根就行了，為了方便，我們每次都選取第一個點當根節點，接下來對于操作1，我們在樹上求一遍前綴和即可，對于操作2，涉及到了路徑上的問題，我們就需要借助LCA把這條路徑先拿出來，然后就很好辦了，分類討論一下，因為第k個點不是在u-lca這條鏈上就是在lca-v這條鏈上，討論一下需要往上跳幾步，然后倍增跳上去就行了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int n;int limit;int deep[N],dp[N][20],sum[N];void dfs(int u,int fa,int dep,int val) {sum[u]=val;deep[u]=dep;dp[u][0]=fa;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=0;i<node[u].size();i++){int v=node[u][i].to;int w=node[u][i].w;if(v==fa)continue;dfs(v,u,dep+1,val+w);} }int LCA(int a,int b) {if(deep[a]<deep[b])swap(a,b);for(int i=limit;i>=0;i--)if(deep[a]-deep[b]>=(1<<i))a=dp[a][i];if(a==b)return a;for(int i=limit;i>=0;i--)if(dp[a][i]!=dp[b][i]){a=dp[a][i];b=dp[b][i];}return dp[a][0]; }int solve(int u,int v,int k) {int lca=LCA(u,v);int len=deep[u]+deep[v]-2*deep[lca]+1;if(deep[u]-deep[lca]>=k-1){int temp=k-1;for(int i=limit;i>=0;i--)if((temp>>i)&1)u=dp[u][i];return u;}else{int temp=len-k;for(int i=limit;i>=0;i--)if((temp>>i)&1)v=dp[v][i];return v;} }void init() {for(int i=1;i<=n;i++)node[i].clear();limit=log2(n)+1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%d",&n);init();for(int i=1;i<n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);node[a].push_back(Node(b,c));node[b].push_back(Node(a,c));}dfs(1,-1,0,0);char s[10];while(scanf("%s",s)&&s[1]!='O'){if(s[0]=='D'){int u,v;scanf("%d%d",&u,&v);printf("%d\n",sum[u]+sum[v]-2*sum[LCA(u,v)]);}else{int u,v,k;scanf("%d%d%d",&u,&v,&k);printf("%d\n",solve(u,v,k));}}}return 0; }

?

總結

以上是生活随笔為你收集整理的SPOJ - QTREE2 Query on a tree II(LCA)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。