西安理工大学2020年程序设计大赛题解

发表于 | 分类于 | 阅读次数: |

A:训练教官

输入样例

1
2
3
2
1 0
0 1

输出样例

1
2.414214

题解

n只有10，所以直接全排列暴力做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

const double inf=1e18;

double x[10];
double y[10];
int vis[10];
double mindis;
int n;

double dist(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}

void print(const int a[]){
    /*
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }printf("\n");
    */
    double dis=0;
    dis+=sqrt(x[a[0]]*x[a[0]]+y[a[0]]*y[a[0]]);
    for(int i=1;i<n;i++){
        dis+=dist(a[i],a[i-1]);
    }
    mindis=min(mindis,dis);
}

void f(int a[],int x){
    if(x==n)print(a);
    else{
        for(int i=x;i<n;i++){
            swap(a[x],a[i]);
            f(a,x+1);
            swap(a[x],a[i]);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%lf%lf",&x[i],&y[i]);
    }
    mindis=inf;

    int a[10];
    for(int i=0;i<n;i++){
        a[i]=i;
    }
    f(a,0);
    printf("%lf\n",mindis);
    return 0;
}

B:假签到题

输入样例

1
2
3
4
3 2 4
4 
4
4

输出样例

1
2

题解

这个题没有什么说的，签到题，有人用double答案错误，计算机精度问题，完全不需要用double

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

using namespace std;
const int maxn=1e7+10;

int a;//限制空间

int main(){
    int n,m,k;
    int num1=0,num2=0;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&a);
        if(a>=k)num1++;
        else num2++;
    }
    int num=0;
    if(num1+num2/5<m){
        printf("-1");
    }else{
        if(num1>=m)printf("%d\n",m);
        else printf("%d\n",num1+(m-num1)*5);
    }
    return 0;
}

C1：逃出地牢

输入样例

1
2
3
4
5
     1
   2   3
1     2    3
   2    1
      1

输出样例

1
10

题解

每行选一个最大的加起来就好了，也没有什么可以解释的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int maxn=500+10;

int a;

int main(){
    int n;
    scanf("%d",&n);
    int num=0;
    for(int i=1;i<=n;i++){
        int x=0;
        for(int j=0;j<=i;j++){
            scanf("%d",&a);
            x=max(x,a); 
        }
        num+=x;
    }
    for(int i=n-1;i>=1;i--){
        int x=0;
        for(int j=0;j<=i;j++){
            scanf("%d",&a);
            x=max(x,a); 
        }
        num+=x;
    }
    printf("%d\n",num);
    return 0;
}

C2：逃出地牢plus

输入样例

1
2
3
4
5
     1
   2   3
1     2    3
   2    1
      1

输出样例

1
10

题解

经典dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

const int maxn=500;

int a[maxn*2+10][maxn+10];

int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int k=0;
    for(int i=n;i<2*n-1;i++){
        k++;
        for(int j=0;j<n;j++){
            if(j>=k)
                scanf("%d",&a[i][j]);
        }
    }

    for(int i=2*n-2;i>=0;i--){
        for(int j=0;j<n;j++){
            a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
        }
    }
    printf("%d\n",a[0][0]);
    return 0;
}

D:作业写不完了

输入样例

1
2

输出样例

1
2
3
4
5
6
7
*  * **** *    ****
*  * *    *    *  *
*  * *    *    *  *
**** **** *    ****
*  * *    *    *
*  * *    *    *
*  * **** **** *

样例解释

这个n控制的是每个字母的端点之间的*字符数目是n个。

1
2
3
4
5
6
7
8
下面这个H的端点用#字符表示，这个只是为了让参赛者更好理解，实际输出不要输出#字符
#  #
*  *
*  *
#**#
*  *
*  *
#  #

题解

模拟，考验代码功底

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

//HELP
int main(){
    int n;
    scanf("%d",&n);

    //1
    printf("*");
    for(int i=0;i<n;i++){
        printf(" ");
    }
    printf("* ");

    printf("*");
    for(int i=0;i<n;i++){
        printf("*");
    }
    printf("* ");

    printf("*");
    for(int i=0;i<n;i++){
        printf(" ");
    }
    printf("  ");

    printf("*");
    for(int i=0;i<n;i++){
        printf("*");
    }
    printf("*\n");

    //2
    for(int j=0;j<n;j++){
        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf("* ");

        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf("  ");

        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf("  ");

        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf("*\n");
    }
    //3
    printf("*");
    for(int i=0;i<n;i++){
        printf("*");
    }
    printf("* ");

    printf("*");
    for(int i=0;i<n;i++){
        printf("*");
    }
    printf("* ");

    printf("*");
    for(int i=0;i<n;i++){
        printf(" ");
    }
    printf("  ");

    printf("*");
    for(int i=0;i<n;i++){
        printf("*");
    }
    printf("*\n");
    //4
    for(int j=0;j<n;j++){
        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf("* ");

        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf("  ");

        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf("  ");

        printf("*");
        for(int i=0;i<n;i++){
            printf(" ");
        }
        printf(" \n");
    }
    //5
    printf("*");
    for(int i=0;i<n;i++){
        printf(" ");
    }
    printf("* ");

    printf("*");
    for(int i=0;i<n;i++){
        printf("*");
    }
    printf("* ");

    printf("*");
    for(int i=0;i<n;i++){
        printf("*");
    }
    printf("* ");

    printf("*");
    for(int i=0;i<n;i++){
        printf(" ");
    }
    printf(" \n");
    return 0;
}

E:禁止套娃

题解

数学问题，答案是3^n，可能多算一下会发现规律，但是要用快速幂来做奥，不然会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

const ll mod=1e9+7;

ll pow_mod(ll a,ll n){
    if(n==0)return 1;
    ll x=pow_mod(a,n/2);
    ll ans=(ll)x*x%mod;
    if(n%2==1)ans=ans*a%mod;
    return ans;
}

int main(){
    ll n;
    scanf("%lld",&n);
    printf("%lld\n",pow_mod(3LL,n));
    return 0;
}

F1:没人比我更懂

题解

数据范围1e18，刚好超出longlong范围，其实算的时候用5 3来算，结果输出+00就好了，注意答案为0输出0，不要输出00

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
typedef long long LL ;
const int N=100010;
 
int main()
{
    unsigned long long n,ans=0;cin >> n;
    if(n&1){
        ans=(n-3)*15+50;
        if(n==1)ans=30;
    }
    else ans=n*15;
    cout << ans ;
    if(ans)cout << "0\n";
    return 0;
}

F2:没人比我更懂Pro

题解

背包dp，可自行百度背包九讲，我就不嫌丑了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

using namespace std;
typedef long long ll;

const ll mod=1e9+7;

struct node{
    int a,b;
    node(){}
    node(int aa,int bb):a(aa),b(bb){}
    bool operator<(node x){
        return a<x.a;
    }
};

int dp[1000][1000];
node a[1010];

int lower_b(int x,int y,int v){
    int m;
    while(x<y){
        m=x+(y-x)/2;
        if(a[m].a>=v)y=m;
        else x=m+1;
    }
    return x;
}

int main(){
    int n,m;

    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a[i].a,&a[i].b);
    }



    sort(a,a+m);
/*
    for(int i=0;i<m;i++){
        printf("%d %d\n",a[i].a,a[i].b);
    }
*/
    for(int j=1;j<=n;j++){
        if(j<a[0].a){
            dp[0][j]=a[0].b;
        }else{
            dp[0][j]=dp[0][j-a[0].a]+a[0].b;
        }
    }
    for(int i=1;i<m;i++){
        for(int j=1;j<=n;j++){
            if(j<a[i].a){
                dp[i][j]=a[i].b;
            }else{
                dp[i][j]=dp[i][j-a[i].a]+a[i].b;
            }
            dp[i][j]=min(dp[i-1][j],dp[i][j]);
        }
    }
/*

    for(int i=0;i<m;i++){
        for(int j=0;j<=n;j++){
            printf("%d ",dp[i][j]);
        }
        printf("\n");
    }
*/
    int q;
    scanf("%d",&q);
    while(q--){
        int v;
        scanf("%d",&v);
        int c=lower_b(0,m,v)-1;
        printf("%d\n",c);
        if(c<0){
            printf("-1\n");
        }else{
            printf("%d\n",dp[c][n]);
        }
    }
    return 0;
}

G:小西的军训

输入样例

1
2
3
4
5
4
M 2 3
C 1 2
M 2 4
C 4 2

输出样例

1
2
-1
1

样例解释

首先所有的同学刚开始都自成一列。

第一个操作M 2 3，就是把2号同学所在的队列接在3号同学的队列后面，因为初始每个队列只有一个同学，所以只需要将2号同学调动到3号同学后面，这时2号和3号同学成为了新的一列。

第二个操作C 1 2，询问1号和2号同学是否在同一列，根据之前的操作他两实际并不是在同一列，所以输出-1。

第三个操作M 2 4，把2号同学所在的队列接在4号同学所在队列的后面，这个时候4号同学的队列里面的同学顺序是这样的4 2 3。

第四个操作C 4 2，询问4号同学和2号同学是否在同一列，实际他两确实在同一列，所以输出他两之间的同学数目。

代码：并查集顺带更新一些数据

没想到没人过，并查集加两个数组顺带更新就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<map>
#include<set>
using namespace std;
inline int read()
{
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
const int maxn=30005;
int pre[maxn],dis[maxn],num[maxn];//pre父亲节点，num这列有多少个，dis本节点距队首多少人
int findd(int x)
{
    if(x!=pre[x])
    {
        int k=pre[x];
        pre[x]=findd(pre[x]);
        dis[x]+=dis[k];
        num[x]=num[pre[x]];
    }
    return pre[x];
}
void update(int x,int y)
{
    int a=findd(x);
    int b=findd(y);
    if(a!=b)
    {
        pre[a]=b;
        dis[a]+=num[b];
        num[b]+=num[a];
        num[a]=num[b];
    }
}
int main()
{
    int t;
    for(int i=0;i<=maxn;i++)
        pre[i]=i,num[i]=1,dis[i]=0;
    t=read();
    while(t--)
    {
        char s[2];
        int x,y;
        scanf("%s",s);
        x=read();y=read();
        if(s[0]=='M')
            update(x,y);
        else
        {
            if(findd(x)!=findd(y))
                cout<<"-1"<<endl;
            else
                cout<<abs(dis[x]-dis[y])-1<<endl;
        }
    }
    return 0;
}

H:教官的决定

输入样例

1
2
3
4
5
6
6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

输出样例

1
2
3
4
2/5
0/1
1/1
4/15

题解

经典莫队，还是没人过，还是了解太少了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int maxn=50000+10;

inline int read()
{
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
struct node
{
    ll l,r;
    ll t;
    ll ans;
}x[maxn];
ll n,m;
ll a[maxn];
ll vis[maxn];
ll now=0;
int block;
int belong[maxn];
bool cmp(node a,node b)
{
    if(belong[a.l]==belong[b.l])
        return a.r<b.r;
    return a.l<b.l;
}
bool cmp1(node a,node b)
{
    return a.t<b.t;
}
void update(int i,int c)
{
    now-=(vis[a[i]]*(vis[a[i]]-1)>>1);
    vis[a[i]]+=c;
    now+=(vis[a[i]]*(vis[a[i]]-1)>>1);
}
ll gcd(ll x,ll y){ return (y)?gcd(y,x%y):x; }
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),vis[a[i]]=0;
    for(int i=0;i<m;i++)
        x[i].l=read(),x[i].r=read(),x[i].t=i;
    block=sqrt(n);
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
    sort(x,x+m,cmp);
    for(int i=x[0].l;i<=x[0].r;i++)
    {
        x[0].ans-=(vis[a[i]]*(vis[a[i]]-1)>>1);
        vis[a[i]]++;
        x[0].ans+=(vis[a[i]]*(vis[a[i]]-1)>>1);
    }
    int l=x[0].l,r=x[0].r;
    now=x[0].ans;
    for(int i=1;i<m;i++)
    {
        while(l<x[i].l)update(l++,-1);
        while(l>x[i].l)update(--l,1);
        while(r<x[i].r)update(++r,1);
        while(r>x[i].r)update(r--,-1);
        x[i].ans=now;
    }
    sort(x,x+m,cmp1);
    for(int i=0;i<m;i++)
    {
        if(x[i].l==x[i].r){
            printf("0/1\n");
            continue;
        }
        ll a=x[i].ans;
        ll b=(x[i].r-x[i].l+1)*(x[i].r-x[i].l)>>1;
        ll c=gcd(a,b);
        printf("%lld/%lld\n",a/c,b/c);
    }
    return 0;
}

I:签到题？

输入样例

1
1 2

输出样例

1
9

题解

这个签到题就是加一个点就相当于横竖都分成了两半，画一画规律就出来了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <cmath>
#include <map>

using namespace std;
int main()
{
    int n;
    cin>>n;
    int x[100005],y[100005];
    x[0]=0,y[0]=0;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    sort(x,x+n+1);
    sort(y,y+n+1);
    int a=unique(x,x+n+1)-x;
    int b=unique(y,y+n+1)-y;
    long long ans=0;
    ans+=(a-1)*(b-1);
    ans+=2*(a+b);
    cout<<ans<<endl;
    return 0;
}

J:听说有人在家变胖了

输入样例

1
2
3
4
3 15
20 21
10 11
30 31

输出样例

1
1066

题解：

分数规划，或者dp都可以做，贪心过了那么多是我万万没想到的，所以加了一组数据，我谢罪，贪心这个题思路完全不行奥，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<algorithm>
#include<iostream>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<cmath>
#include<stack>
#include<ctime>
#include<map>
#include<set>
#define ll long long
using namespace std;
const int maxn=1e6+10;

inline int read()
{
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n,w;
int a[1000],b[1000];
double f[1000];
bool judge(double mid)
{
    for(int i=1;i<=w;i++) f[i]=-1e9;
    for(int i=1;i<=n;i++)
    {
        for(int j=w;j>=0;j--)
        {
            int jj=min(j+a[i],w);
            f[jj]=max(f[jj],f[j]+b[i]-a[i]*mid);
        }
    }
    return f[w]>0;
}
int main()
{
    n=read(),w=read();
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    double l=0,r=1000;
    for(int i=0;i<100;i++)
    {
        double mid=(l+r)*0.5;
        if(judge(mid)) l=mid;
        else r=mid;
    }
    cout<<(int)floor(l*1000)<<endl;
    return 0;
}

K，防ak题

点分治

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
using namespace std;
#define maxn 100005
#define inf 0x3f3f3f3f
#define ll long long
ll n,k,cnt,root,ans,maxx,head[maxn],size[maxn],son[maxn],vis[maxn],num[maxn];
struct edge{
    ll to,next,val;
}e[maxn*4];
 
vector<ll>dis;
 
void add(ll u,ll v,ll val)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].val=val;
    head[u]=cnt;
}
void dfs_size(ll u,ll fa)//求各点子树大小
{
    size[u]=1;son[u]=0;
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].to;
        if(v!=fa&&!vis[v])
        {
            dfs_size(v,u);
            size[u]+=size[v];
            son[u]=max(son[u],size[v]);
        }
    }
}
void dfs_root(ll N,ll u,ll fa)//求重心
{
    son[u]=max(son[u],N-size[u]);
    if(maxx>son[u])
    {
        root=u;
        maxx=son[u];
    }
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].to;
        if(v!=fa&&!vis[v])
        dfs_root(N,v,u);
    }
}
void dfs_dis(ll u,ll fa,ll val)//求出所有点到根的距离
{
    val%=2020;
    num[val]++;
    //dis.push_back(val);
    for(ll i=head[u];i;i=e[i].next)
    {
        ll v=e[i].to;
        if(v!=fa&&!vis[v])
        dfs_dis(v,u,val+e[i].val);
    }
}
ll cal(ll u,ll val)//计算小于等于k的路径数
{
    for(ll i=0;i<2020;i++)
    num[i]=0;
    //dis.clear();
    dfs_dis(u,0,val);
    //sort(dis.begin(),dis.end());
    ll ret=0;
    for(ll i=1;i<2020;i++)//two-pointer
    {
        if(num[i]&&num[2020-i])ret+=num[i]*num[2020-i];
    }
    ret/=2;
    ret+=num[0]*(num[0]-1)/2;
 
    return ret;
}
void dfs(ll u)
{
    dfs_size(u,0);
    maxx=inf;
    dfs_root(size[u],u,0);
    ans+=cal(root,0);//此时算出的路径数是包括没经过这个根的路径数，后面需要减去这种的路径数
    vis[root]=1;//将选的roo又被遍历t标记，防止其在之后的分治过程中
    for(ll i=head[root];i;i=e[i].next)
    {
        ll v=e[i].to,val=e[i].val;
        if(!vis[v])
        {
            ans-=cal(v,val);//子树所有边加上dis(u,v)后满足的路径数就是需要减去的路径数
            dfs(v);//递归分治
        }
    }
}
 
int main()
{
    while(scanf("%lld",&n)!=EOF)
    {
        ll u,v,val;
        for(ll i=1;i<=n;i++)
        head[i]=vis[i]=0;
        cnt=ans=0;
        for(ll i=1;i<n;i++)
        {
            scanf("%lld%lld%lld",&u,&v,&val);
            add(u,v,val);
            add(v,u,val);
        }
        dfs(1);
        printf("%lld\n",ans);
    }
    return 0;
}