병렬 모음_레코드 포인트에서 루트까지의 거리
제목 설명은 모두 n대의 서버가 있는데 서버 그룹은 일부 뿌리 나무로 구성된 숲이라고 볼 수 있다.처음에 n대의 서버가 서로 통하지 않았고 모든 서버는 자신을 루트 서버로 했다.파추리는 두 가지 조작을 할 것이다. U u v w, v 결점의 루트 서버 루트(v)를 u 결점의 루트 서버 루트(u)의 하위 결점으로 루트(u)에 연결하고 루트(v)에서 루트(u)까지의 거리는 w이다.만약root(v)=root(u)이면 아무런 조작도 하지 않습니다(주의, 이때 root(v)의 모든 하위 결점의 루트 결점은 루트(u)로 바뀝니다. 예를 들어 루트(v)는 루트(u)로 바뀝니다.C u, 쿼리를 표시하고 루트 (u) 까지의 거리를 되돌려줍니다.
입력 형식의 첫 번째 행위는 두 개의 정수 n, m(1<=n<=100000, 1<=m<=600000)로 서버 개수와 조작 횟수를 나타낸다.다음 m줄은 각 줄의 시작은'U'또는'C'로 조작 종류를 나타낸다. 만약에 시작자가'U'이면 조작 1을 나타낸다.다음은 세 개의 u, v, w(1<=u, v<=n, 1<=w<=100)를 따라 루트(v)를 루트(u)의 자결점으로 루트(u)에 연결하고 루트(v)에서 루트(u)까지의 거리는 w이다.root(v)==root(u)이면 아무런 조작도 하지 않습니다.시작 문자가 "C"이면 작업 2를 나타냅니다.다음은 u(1<=u<=n)를 따라 결점 u에서 결점까지의 거리를 조회합니다.출력 형식은 매 조작 2에 대해 한 줄의 정수를 출력하여 조회의 결점에서 루트 결점까지의 거리를 나타낸다.입력 5 6 C 4 U 4 2 51 C 2 U 3 1 2 U 3 4 6 C 2 출력 0 51 57
#include
#include
using namespace std;
#define maxn 100010
int fa[maxn];
int dis[maxn];
int father(int u)
{
if(u==fa[u]) return u;
int root=father(fa[u]);
dis[u]=dis[u]+dis[fa[u]];
return fa[u]=root;
}
void connect(int u,int v,int w)
{
int fu=father(u);
int fv=father(v);
if(fu==fv) return ;
fa[fu]=fv;
dis[fu]=w;
}
int main()
{
int n,m,u,v,w;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
fa[i]=i;
dis[i]=0;
}
char s;
getchar();
for(int i=1;i<=m;i++)
{
s=getchar();
if(s=='C')
{
scanf("%d",&u);
father(u);
printf("%d
",dis[u]);
}
else
{
scanf("%d%d%d",&u,&v,&w);
connect(v,u,w);
}
getchar();
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
