P
r
o
b
l
e
m
\mathrm{Problem}
Problem
S
o
l
u
t
i
o
n
\mathrm{Solution}
Solution
对于一棵树，我们考虑新添加的边。
显然添加的边只有祖先关系，如果没有祖先关系必然会从某一叉经过这条边，那么这条边会在Dfs的过程被遍历到、成为树边。对于存在祖先关系的边，若存在一条非树边，对于
w
w
w 是
v
v
v 的子节点，则必然有
a
w
>
a
v
a_w>a_v
aw>av。如下图所示： 现在，我们就将问题转化为除根节点外，每个数的子树有几个节点比它大，这对应了树上的逆序对问题，树状数组维护即可。
KaTeX parse error: Undefined control sequence: \mathem at position 1: \̲m̲a̲t̲h̲e̲m̲{Code}
#include <bits/stdc++.h>
using namespace std
;
const int N
= 2e5;
const int P
= 1e9 + 7;
int n
, res(1);
vector
< int > a
[N
];
int read(void)
{
int s
= 0, w
= 0; char c
= getchar();
while (!isdigit(c
)) w
|= c
== '-', c
= getchar();
while (isdigit(c
)) s
= s
*10+c
-48, c
= getchar();
return w
? -s
: s
;
}
struct Bit
{
#define lowbit(x) (x & -x)
int S
[N
* 10] = {};
void add(int x
, int v
) {
for (int i
=x
;i
<=n
;i
+=lowbit(i
))
S
[i
] += v
;
return;
}
int ask(int x
) {
int res
= 0;
for (int i
=x
;i
>=1;i
-=lowbit(i
))
res
+= S
[i
];
return res
;
}
} tree
;
int power(int a
, int b
)
{
int res
= 1;
while (b
> 0) {
if (b
& 1) res
= 1LL * res
* a
% P
;
a
= 1LL * a
* a
% P
, b
>>= 1;
}
return res
;
}
void Dfs(int x
, int fa
)
{
if (x
> 1) tree
.add(x
, 1);
res
= 1LL * res
* power(2, tree
.ask(x
-1)) % P
;
for (int i
=0;i
<a
[x
].size();++i
)
{
int y
= a
[x
][i
];
if (y
== fa
) continue;
Dfs(y
, x
);
}
if (x
> 1) tree
.add(x
, -1);
return;
}
int main(void)
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
n
= read();
for (int i
=1;i
<n
;++i
)
{
int x
= read(), y
= read();
a
[x
].push_back(y
);
a
[y
].push_back(x
);
}
Dfs(1, 0);
cout
<< res
<< endl
;
return 0;
}
