比赛 |
noip2016普及练习2 |
评测结果 |
AAAAAAAA |
题目名称 |
保卫钓鱼岛! |
最终得分 |
100 |
用户昵称 |
明天 |
运行时间 |
0.063 s |
代码语言 |
C++ |
内存使用 |
1.24 MiB |
提交时间 |
2016-11-07 20:28:45 |
显示代码纯文本
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
-
- struct node
- {
- int x,next;
- };
-
- const int maxn=10000+1;
- const int maxm=100000+1;
-
- int n,m;
- int h[maxn],len;
- node table[maxm];
-
- int x,y,z;
- bool used[maxn];
- int w[maxn],depth[maxn],father[maxn];
- int ans;
- long long total;
-
- void dfs(int x);
- inline int getint()
- {
- int x=0;
- char ch=getchar();
- while (ch<'0' || ch>'9')
- ch=getchar();
- while (ch>='0' && ch<='9')
- {
- x=x*10+ch-'0';
- ch=getchar();
- }
- return x;
- }
- inline void add1(int i, int j)
- {
- len++;
- table[len].x=j; table[len].next=h[i];
- h[i]=len;
- }
- int main()
- {
- freopen("diaoyu.in","r",stdin);
- freopen("diaoyu.out","w",stdout);
-
- scanf("%d%d",&n,&m);
- for (int k=1; k<n; k++)
- {
- x=getint(); y=getint(); z=getint();
- add1(x,y);
-
- w[y]=z; father[y]=x;
- }
-
- dfs(1);
-
- for (int k=1; k<=m; k++)
- {
- x=getint(); y=getint();
-
- if (x==y) continue;
- int t=0;;
- while (depth[y]>depth[x])
- {
- t+=w[y];
- y=father[y];
- }
- if (x==y)
- {
- total+=t; ans++;
- }
- }
-
- cout<<ans<<endl;
- cout<<total<<endl;
-
- return 0;
- }
-
- void dfs(int x)
- {
- int p=h[x];
- while (p)
- {
- int u=table[p].x;
- if (!used[u])
- {
- used[u]=true; depth[u]=depth[x]+1;
- dfs(u);
- }
- p=table[p].next;
- }
- }