#include <bits/stdc++.h>
using namespace std;
const int N = 300050;
const int M = N*2;
int n,m,a[N],t1,t2;
int head[N], cnt;
struct Edge{
	int u,v,next;
}edge[M];
void add(int u, int v){
	edge[++cnt].u = u;
	edge[cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
int fa[N][31], d[N];
void dfs(int u, int faa){
	fa[u][0] = faa, d[u] = d[faa] + 1;
	for(int i = 1; i <=25; i++){
		fa[u][i] = fa[ fa[u][i - 1] ][i - 1];
	}
	for(int i = head[u]; i ; i = edge[i].next){
		int v = edge[i].v;
		if(v == faa)continue;
		dfs(v, u);
	}
} 
int lca(int x, int y){
	if(d[x] < d[y])swap(x,y);
	for(int i = 25; i >= 0; i--){
		if(d[ fa[x][i] ] >= d[y]) x = fa[x][i];
	}
	if(x == y)return x;
	for(int i = 25; i >= 0; i--){
		if(fa[x][i] != fa[y][i]){
			x = fa[x][i], y = fa[y][i];
		}
	}
	return fa[x][0];
}
int num[N];
int dfs2(int u, int faa){
	for(int i = head[u]; i ; i = edge[i].next){
		int v = edge[i].v;
		if(v == faa)continue;
		dfs2(v, u);
		num[u] += num[v];
	}
}
int main(){
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>> a[i];
	}
	for(int i = 1; i < n; i++){
		cin>> t1>> t2;
		add(t1, t2);
		add(t2, t1);
	}
	dfs(1, 0);
	for(int i = 1; i <= n - 1; i++){
		int u = a[i], v = a[i + 1];
		int t = lca(u, v);
		num[ fa[t][0] ]	-= 1;
		num[ t ] -= 1;
		num[ u ] += 1;
		num[ v ] += 1;
	}
	dfs2(1,0);
	for(int i = 2; i <= n; i++){
		num[a[i]]--;
	}
	for(int i = 1; i <= n; i++){
		cout<<num[i]<<endl;
	}
}

#include <bits/stdc++.h>
using namespace std;
const int sHo = 20001;
int n, k, m, fa[sHo], flag[sHo], ans, cnt;
struct node {
    int u, v, c1, c2, num;
} road[sHo];
bool cmp1(node x, node y) { return x.c1 < y.c1; }
bool cmp2(node x, node y) { return x.c2 < y.c2; }
int find(int x) {
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> m;
    m--;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        cin >> road[i].u >> road[i].v >> road[i].c1 >> road[i].c2;
        road[i].num = i;
    }
    sort(road + 1, road + 1 + m, cmp1);
    for (int i = 1; i <= m; i++) {
        int p = find(road[i].u);
        int q = find(road[i].v);
        if (p != q) {
            fa[q] = p;
            ans = max(ans, road[i].c1);
            flag[road[i].num] = 1;
            cnt++;
        }
        if (cnt == k) {
            k = i;
            break;
        }
    }
    sort(road + k + 1, road + 1 + m, cmp2);
    for (int i = k + 1; i <= m; i++) {
        int p = find(road[i].u);
        int q = find(road[i].v);
        if (p != q) {
            fa[q] = p;
            ans = max(ans, road[i].c2);
            flag[road[i].num] = 2;
        }
    }
    cout << ans << '\n';
    for (int i = 1; i <= m; i++)
        if (flag[i] > 0)
            cout << i << ' ' << flag[i] << '\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
long long n, m, x[1001], y[1001], xxx, yyy, pos;
double a[1001][1001], dis[1001], cost;
bool vis[1001];
double pre(int s, int t) {
    long long a = x[s], b = y[s], c = x[t], d = y[t];
    double ans = sqrt(abs(a - c) * abs(a - c) + abs(b - d) * abs(b - d));
    return ans;
}
void prim() {
    for (int i = 0; i <= 1000; i++) dis[i] = INT_MAX;
    dis[1] = 0;
    for (int i = 1; i < n; i++) {
        pos = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (pos == 0 || dis[j] < dis[pos]))
                pos = j;
        vis[pos] = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j])
                dis[j] = min(dis[j], a[pos][j]);
    }
}
int main() {
    for (int i = 0; i <= 1000; i++)
        for (int j = 0; j <= 1000; j++) a[i][j] = INT_MAX;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) a[i][j] = pre(i, j);
    for (int i = 1; i <= m; i++) {
        cin >> xxx >> yyy;
        a[xxx][yyy] = 0;
        a[yyy][xxx] = 0;
    }
    prim();
    for (int i = 1; i <= n; i++) cost += dis[i];
    cout << fixed << setprecision(2) << cost;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define stoSHYorz 1001
#define int long long
int n, m, x[stoSHYorz], y[stoSHYorz], xxx, yyy, pos;
double a[stoSHYorz][stoSHYorz], dis[stoSHYorz], cost;
bool vis[stoSHYorz];
double pre(int s, int t) {
    int a = x[s], b = y[s], c = x[t], d = y[t];
    double ans = sqrt(abs(a - c) * abs(a - c) + abs(b - d) * abs(b - d));
    return ans;
}
void prim() {
    for (int i = 0; i <= 1000; i++) dis[i] = 15938321;
    dis[1] = 0;
    for (int i = 1; i < n; i++) {
        pos = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (pos == 0 || dis[j] < dis[pos]))
                pos = j;
        vis[pos] = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j])
                dis[j] = min(dis[j], a[pos][j]);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (int i = 0; i <= 1000; i++)
        for (int j = 0; j <= 1000; j++) a[i][j] = 15938321;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) a[i][j] = pre(i, j);
    for (int i = 1; i <= m; i++) {
        cin >> xxx >> yyy;
        a[xxx][yyy] = 0;
        a[yyy][xxx] = 0;
    }
    prim();
    for (int i = 1; i <= n; i++) cost += dis[i];
    cout << fixed << setprecision(2) << cost;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define stoSHYorz 1001
#define int long long
int n, temp, a[stoSHYorz][stoSHYorz], dis[stoSHYorz], pos, cost;
bool vis[stoSHYorz];
void prim() {
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    for (int i = 1; i < n; i++) {
        pos = 0;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (pos == 0 || dis[j] < dis[pos]))
                pos = j;
        vis[pos] = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j])
                dis[j] = min(dis[j], a[pos][j]);
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    memset(a, 0x3f, sizeof a);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        a[i][n + 1] = temp;
        a[n + 1][i] = temp;
    }
    for (int i = 1; i <= n + 1; i++) a[i][i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) cin >> a[i][j];
    n++;
    prim();
    for (int i = 1; i <= n; i++) cost += dis[i];
    cout << cost;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n,m,father[5001],p,q,h=0,ans=0,cn;          
struct node{
	int f,t,c;
}a[200001];                               
bool cmp1(node a,node b){
	return a.c<b.c;
}
int find(int x){
	if (father[x]==x){
		return x;
	}
	else{
		father[x]=find(father[x]);
		return father[x];
	}
}
void add(int x,int y) {
	p=find(x);q=find(y);
	if (p!=q){
		father[p]=q;
	}
}
int main(){
	cin>>n>>m;
	cn=n;                 
	for (int i=1;i<=n;i++){
		father[i]=i;            
	}
	for (int i=1;i<=m;i++){
		cin>>a[i].f>>a[i].t>>a[i].c;
	}
	sort(a+1,a+m+1,cmp1);         
	n--;
	while (n>0){
		h++;
		if (h>m){
			cout<<"orz";
			return 0;
		}
		if (find(a[h].f)==find(a[h].t)){
			continue;
		}
		else{
			add(a[h].f,a[h].t);                   
			n--;
			ans+=a[h].c;                      
		}
	}
	cout<<ans;
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int u,dis;
	bool operator <(const node a)const
	{
		return dis>a.dis;
	}
};
struct edge
{
	int v,w;
};
vector <edge> g[100005];
int dis[100005],s;
priority_queue <node> q;
void dijkstra()
{
	memset(dis,0x7f,sizeof(dis));
	dis[s]=0;
	q.push((node){s,0});
	while(!q.empty())
	{
		node front=q.top();
		q.pop();
		if(dis[front.u]!=front.dis)continue;
		for(int i=0;i<g[front.u].size();i++)
		{
			int v=g[front.u][i].v,w=g[front.u][i].w;
			if(dis[v]>dis[front.u]+w)
			{
				dis[v]=dis[front.u]+w;
				q.push((node){v,dis[v]});
			}
		}
	}
}
int main()
{
	int n,m;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((edge){v,w});
	}
	dijkstra();
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}