SPOJ 913. Query on a tree II
5090 단어 query
You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value assigned to it, representing its length.
We will ask you to perfrom some instructions of the following form:
Example:N = 6 1 2 1//edge connects node 1 and node 2 has cost 1 2 4 1 2 5 2 1 3 1 3 6 2 Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6 DIST 4 6 : answer is 5 (1 + 1 + 1 + 2 = 5) KTH 4 6 4 : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3)
Input
The first line of input contains an integer t, the number of test cases (t <= 25). t test cases follow.
For each test case:
There is one blank line between successive tests.
Output
For each "DIST" or "KTH" operation, write one integer representing its result.
Print one blank line after each test.
Example
Input:
1
6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
DIST 4 6
KTH 4 6 4
DONE
Output:
5
3
-------------------------------------------------------------------
: , ,DIST(i,j) i j ,KTH(i,j,k) i j k 。
: 。 2^i 。 DIST , lca, 。 KTH , lca, lca lca 。 , ,RE 。
#include <stdio.h>
#include <string.h>
#include <vector>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=200005;
int n,eid;
int head[N],ed[N<<1],val[N<<1],nxt[N<<1];
vector<int>fa[N];
int sta[N],top,dep[N],dis[N];
void addedge(int s,int e,int v){
ed[eid]=e;val[eid]=v;nxt[eid]=head[s];head[s]=eid++;
}
void dfs(int s,int f,int d,int ds){
fa[s].clear();int k=1;dep[s]=d;dis[s]=ds;
while(top-k>=0){
fa[s].push_back(sta[top-k]);k*=2;
}
sta[top++]=s;
for(int i=head[s];~i;i=nxt[i]){
int e=ed[i],v=val[i];
if(e!=f)dfs(e,s,d+1,ds+v);
}
top--;
}
int lca(int a,int b){
if(a==b)return a;
if(dep[b]>dep[a])swap(a,b);
while(dep[a]>dep[b]){
int len=fa[a].size(),le=0,ri=len,mid;
while(mid=(le+ri)>>1,ri>le){
if(dep[fa[a][mid]]>=dep[b])le=mid+1;
else ri=mid;
}
a=fa[a][ri-1];
}
if(a==b)return a;
while(1){
int len=fa[a].size(),le=0,ri=len,mid;
while(mid=(le+ri)>>1,ri>le){
if(fa[a][mid]!=fa[b][mid])le=mid+1;
else ri=mid;
}
if(ri==0)return fa[a][ri];
a=fa[a][ri-1];b=fa[b][ri-1];
}
return a;
}
int kth(int a,int b,int k){
int r=lca(a,b);
if(dep[a]-dep[r]+1>=k){
int u=dep[a]-k+1;
while(1){
if(u==dep[a])return a;
int len=fa[a].size(),le=0,ri=len,mid;
while(mid=(le+ri)>>1,ri>le){
if(dep[fa[a][mid]]>=u)le=mid+1;
else ri=mid;
}
a=fa[a][ri-1];
}
}
else{
int u=k-dep[a]+dep[r]*2-1;
while(1){
if(u==dep[b])return b;
int len=fa[b].size(),le=0,ri=len,mid;
while(mid=(le+ri)>>1,ri>le){
if(dep[fa[b][mid]]>=u)le=mid+1;
else ri=mid;
}
b=fa[b][ri-1];
}
}
}
int main(){
// freopen("/home/axorb/in","r",stdin);
int T;scanf("%d",&T);
while(T--){
eid=0;clr(head,-1);scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);addedge(b,a,c);
}
top=0;dfs(1,-1,1,0);
// for(int i=1;i<=n;i++)printf("%d %d %d
",i,fa[i].size(),dep[i]);
char ss[20];
while(scanf("%s",ss),ss[1]!='O')
if(ss[1]=='I'){
int a,b;scanf("%d%d",&a,&b);
int r=lca(a,b);
printf("%d
",dis[a]+dis[b]-2*dis[r]);
}
else{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
printf("%d
",kth(a,b,c));
}
puts("");
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
빠른 팁!!!안녕하세요 여러분 👋 요청을 할 때 모든 구성 요소에 동일한 코드를 작성하는 데 정말 지쳤습니다. 나는 일을 단순하게 만들고 싶고 내 생각에 당신도 원할 것입니다. 그런 것들에 대한 팁을 보려면 내 예를 확인하십시오...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.