牛客练习赛23 F 托米的游戏

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <string>
 6 #include <set>
 7 #include <map>
 8 #include <list>
 9 #include <stack>
10 #include <queue>
11 #include <vector>
12 #include <algorithm>
13 #include <iostream>
14 using namespace std;
15 #define ll long long
16 #define minv 1e-6
17 #define inf 1e9
18 const ll mod=998244353;
19 const long maxn=1e5+5;
20  
21 vector<int>e[maxn];
22 bool vis[maxn]={0};
23 ll result=0,x,y;
24  
25 void gcd(ll a,ll b)
26 {
27     if (b==0)
28     {
29         x=1;
30         y=0;
31     }
32     else
33     {
34         gcd(b,a%b);
35         ll r;
36         r=x;
37         x=y;
38         y=r-a/b*y;
39     }
40 }
41  
42 ll ni(ll s)
43 {
44     gcd(mod,s%mod);
45     return (y%mod+mod)%mod;
46 }
47  
48 void dfs(int d,int dep)
49 {
50     vis[d]=1;
51     result=(result+ni(dep))%mod;
52     vector<int>::iterator i;
53     for (i=e[d].begin();i!=e[d].end();i++)
54         if (!vis[*i])
55             dfs(*i,dep+1);
56 }
57  
58 int main()
59 {
60     int n,i,x,y;
61     scanf("%d",&n);
62     for (i=1;i<n;i++)
63     {
64         scanf("%d%d",&x,&y);
65         e[x].push_back(y);
66         e[y].push_back(x);
67     }
68     dfs(1,1);
69     printf("%lld",result);
70     return 0;
71 }
72 /*
73 3
74 2 1
75 3 2
76 */