Submission #12141534


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 1000000007
#define pb push_back
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector< pi > 
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL)
const int N=200003;
vi v[N];
ll c[N],a[N],val[N],res[N],sub[N];
int dfs(int x,int p)
{
    for(int y:v[x])
        if(y!=p)
            sub[x]+=dfs(y,x);
    sub[x]+=1;
    return sub[x];
}
void solv(int x,int p)
{
    ll n=val[c[x]];
    ll add=(n-sub[x]+1)*sub[x],sm=0;
    for(int y:v[x])
    {
        if(y==p) continue;
        add+=1ll*sub[y]*sm;
        sm+=sub[y];
    }
    res[c[x]]+=add;
    //val[c[x]]=sub[x]-1;
    for(int y:v[x])
    {
        if(y==p) continue;
        val[c[x]]=sub[y];
        solv(y,x);
    }
    val[c[x]]=n-sub[x];
}
int main()
{
    int n,x,y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        val[i]=n;
    }
    for(int i=1;i<n;i++)
    {
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,0);
    solv(1,0);
    for(int i=1;i<=n;i++)
    {
        cout<<res[i]<<'\n';
    }
    return 0;
}

Submission Info

Submission Time
Task F - path pass i
User sarwarkhan
Language C++ (GCC 9.2.1)
Score 600
Code Size 1184 Byte
Status AC
Exec Time 264 ms
Memory 36384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 5
AC × 24
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt
All line_01.txt, line_3_01.txt, random_01.txt, random_02.txt, random_03.txt, random_100_01.txt, random_100_02.txt, random_10_01.txt, random_10_02.txt, random_1_01.txt, random_1_02.txt, random_2_01.txt, random_2_02.txt, random_2_03.txt, random_3_01.txt, random_3_02.txt, random_3_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, sample_05.txt, star_01.txt, star_3_01.txt
Case Name Status Exec Time Memory
line_01.txt AC 183 ms 36384 KB
line_3_01.txt AC 155 ms 34716 KB
random_01.txt AC 258 ms 20956 KB
random_02.txt AC 259 ms 20956 KB
random_03.txt AC 264 ms 21000 KB
random_100_01.txt AC 233 ms 19356 KB
random_100_02.txt AC 235 ms 19384 KB
random_10_01.txt AC 222 ms 19204 KB
random_10_02.txt AC 243 ms 19292 KB
random_1_01.txt AC 227 ms 19300 KB
random_1_02.txt AC 227 ms 19172 KB
random_2_01.txt AC 230 ms 19356 KB
random_2_02.txt AC 221 ms 19336 KB
random_2_03.txt AC 228 ms 19324 KB
random_3_01.txt AC 230 ms 19240 KB
random_3_02.txt AC 223 ms 19308 KB
random_3_03.txt AC 225 ms 19240 KB
sample_01.txt AC 12 ms 8152 KB
sample_02.txt AC 6 ms 8260 KB
sample_03.txt AC 5 ms 8144 KB
sample_04.txt AC 5 ms 8340 KB
sample_05.txt AC 6 ms 8152 KB
star_01.txt AC 150 ms 21112 KB
star_3_01.txt AC 119 ms 19752 KB