UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214235#2763. 幻想乡的拜访nullptr_qwq1002009ms65736kbC++115.5kb2024-11-16 18:55:262024-11-16 23:10:58

answer

// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=1e9+7,maxn=1000005;
inline int qpow(int x,ll y){
	int rt=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) rt=1ll*rt*x%mod;
	return rt;
}
inline void inc(int &x,const int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,const int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,const int y){ x=1ll*x*y%mod; }
inline int add(const int x,const int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(const int x,const int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(const int x,const int y){ return 1ll*x*y%mod; }
int siz[maxn],sum,n,ans;
vector<int>g[maxn];
void dfs(int u,int fa=0){
	siz[u]=u;
	for(auto v:g[u])if(v^fa)dfs(v,u),inc(siz[u],siz[v]);
	if(fa)inc(ans,1ll*siz[u]*sub(sum,siz[u])%mod);
}
void solve(){
	cin>>n;
	F(i,1,n)inc(sum,i);
	F(i,1,n-1){int u,v; cin>>u>>v;g[u].push_back(v),g[v].push_back(u);}
	dfs(1),cout<<ans;
}
signed main(){
	// ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 8ms
memory: 24616kb

input:

200
20 160
90 160
5 90
78 90
186 90
149 90
104 78
136 160
106 78
100 106
168 90
30 5
85 136
28 149
1...

output:

104425891

result:

ok single line: '104425891'

Test #2:

score: 10
Accepted
time: 4ms
memory: 24612kb

input:

200
49 91
20 91
147 91
131 20
36 131
9 131
51 147
173 51
32 36
169 51
180 51
2 91
133 2
72 20
14 169...

output:

145567217

result:

ok single line: '145567217'

Test #3:

score: 10
Accepted
time: 9ms
memory: 24616kb

input:

200
44 72
187 72
115 72
124 115
80 124
34 72
22 115
162 34
123 44
93 22
135 80
5 124
112 72
76 187
3...

output:

226420652

result:

ok single line: '226420652'

Test #4:

score: 10
Accepted
time: 3ms
memory: 24728kb

input:

3000
940 1649
220 1649
1438 1649
2264 1649
1467 940
1825 220
1646 940
571 220
1419 220
2509 1438
264...

output:

781596579

result:

ok single line: '781596579'

Test #5:

score: 10
Accepted
time: 3ms
memory: 24728kb

input:

3000
2156 216
2422 2156
2801 216
2504 2156
2701 2156
2582 2801
1558 2156
864 2582
737 864
2919 1558
...

output:

236427659

result:

ok single line: '236427659'

Test #6:

score: 10
Accepted
time: 9ms
memory: 24724kb

input:

3000
2966 2885
2657 2885
2613 2966
1686 2613
2803 2885
191 2657
2824 2657
675 2657
2693 191
2798 191...

output:

688220644

result:

ok single line: '688220644'

Test #7:

score: 10
Accepted
time: 467ms
memory: 65712kb

input:

1000000
984750 990109
970095 984750
996126 970095
998081 990109
987074 970095
962711 970095
916630 9...

output:

192557796

result:

ok single line: '192557796'

Test #8:

score: 10
Accepted
time: 651ms
memory: 65564kb

input:

1000000
947305 936749
948062 947305
970449 947305
988744 948062
998703 988744
986194 947305
997762 9...

output:

160385007

result:

ok single line: '160385007'

Test #9:

score: 10
Accepted
time: 461ms
memory: 65736kb

input:

1000000
952012 962256
982471 962256
955412 952012
953636 962256
991390 952012
998704 953636
999294 9...

output:

308556344

result:

ok single line: '308556344'

Test #10:

score: 10
Accepted
time: 394ms
memory: 65692kb

input:

1000000
900864 972452
986047 900864
953966 972452
977801 986047
997024 972452
954755 953966
999240 9...

output:

201471911

result:

ok single line: '201471911'