C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 3105 小明喜欢树 V2

Problem

小明非常喜欢树,有一天小明得到这样一棵树,每个树节点都有一个编号,有n个节点的树的编号为1到n,每个编号代表该节点的海拔高度,现在小明要在这颗树上找到一些路径,从起点到终点需要满足海拔先单调上升后单调下降的性质,起点或终点不同即为不同的路径,问满足条件的路径有多少条,聪明的你可以帮助小明解决这个问题吗?

Solution

计算一个点周围小于等于它的点,包括它自身。然后对于每一个点,连通的小于它的点,之前算出来的值(可以认为这个值是这条分支的起点/终点数)两两相乘。

code1只是简单记忆化了一下,code2融合进计算值里,由于每次只是和前面的sum,不是和总sum相乘,所以答案要*2.

Code1

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
#include<stdio.h>
using namespace std;
#define db double
#define ll long long
inline int rd(){
int x=0;
char ch=0;
while(ch<'0'||ch>'9') {ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
const int MAXN=1000020;
int n;
int g[MAXN];
struct E{
int u,v,nex;
}e[MAXN*2];
ll f[MAXN];
ll dfs(int u){
ll sum=0;
for(int i=g[u];i>0;i=e[i].nex){
int v=e[i].v;
if(v<u) sum+=f[v]==0?dfs(v):f[v];
}
return f[u]=sum+1;
}
ll ans=0;
int main(){
//io_opt;
n=rd();
int x,y;
for(int i=1;i<n;i++){
x=rd();
y=rd();
e[i]=(E){x,y,g[x]};g[x]=i;
e[i+n-1]=(E){y,x,g[y]};g[y]=i+n-1;
}
for(int i=n;i>=1;i--){
if(!f[i]) dfs(i);
}
for(int i=1;i<=n;i++){
ll sum=0;
for(int j=g[i];j>0;j=e[j].nex){
int v=e[j].v;
if(v<i) sum+=f[v];
}
for(int j=g[i];j>0;j=e[j].nex){
int v=e[j].v;
if(v<i) ans+=f[v]*(sum-f[v]);
}
}
printf("%lld\n",ans);
return 0;
}

code2

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
#include<stdio.h>
using namespace std;
#define db double
#define ll long long
const int MAXN=1000020;
int n;
int g[MAXN];
struct E{
int u,v,nex;
}e[MAXN*2];
int f[MAXN];
int sum[MAXN];
ll ans=0;
int dfs(int u){
for(int i=g[u];i>0;i=e[i].nex){
int v=e[i].v;
if(v<u){
sum[u]+=f[v]==0?dfs(v):f[v];
ans+=f[v]*(ll)(sum[u]-f[v]);
}
}
return f[u]=sum[u]+1;
}
int main(){
//io_opt;
scanf("%d",&n);
int x,y;
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
e[i]=(E){x,y,g[x]};g[x]=i;
e[i+n-1]=(E){y,x,g[y]};g[y]=i+n-1;
}
for(int i=n;i>=1;i--){
if(!f[i]) dfs(i);
}
printf("%lld\n",ans*2);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/15019/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!