缆车
1612: 缆车
时间限制: 3 Sec 内存限制: 128 MB
提交: 4 解决: 2
[提交] [状态] [讨论版]
题目描述
在远离大陆的太平洋上，有一个风景优美的小岛。传说，小岛上的文明是这样发展起来的。
第一代人沿着岛的坡度选择了n 个定居点，编号为1,2,…,n. 其中编号 i 定居点的高度就是i米。他们在定居点的附近修建了房屋，开辟了农田,种植了植物。
第二代人在 n 个定居点之间修建了n-1条小路，每条小路连接两个定居点，且任意两个定居点之间都可以通过小路相互到达,互通有无。
各个定居点不仅高度不同,而且距离非常远.随着技术的提高,第三代人将盘岛小路改造成可以通缆车的道路。这样不同定居点的人们不费力气就可以借助缆车，自由地到达任何一个定居点。
为了纪念开辟文明的先辈，每年，小岛上都会举行一种特殊的仪式。每年的仪式会选择两个定居点x, y，人们将自己的思念和祝愿写成信件放入缆车，缆车将从定居点x 出发，沿着唯一的路径驶向定居点y。为了体会到翻山越岭的感觉, 岛民们希望缆车行车路线满足如下条件:
缆车依次经过若干定居点a1, a2，…, ak，岛民们认为，如果存在i,在满足 1<i<k 条件下，
a1< a2<……< ai 且 ai >ai+1 ……> ak
a1可以作为出发点，ak 可以作为终止点。
岛民想要知道，存在多少种不同路径的仪式方案？ 所谓两个仪式方案不同，是指在满足约束条件下，如果他们的出发节点不同，或者结束点不同。
输入
第一行： T 表示以下有T组测试数据 （ 1≤ T ≤ 5 ）
对每组数据，第1行： 一个整数n表示定居点个数。 接下来有n-1行，每行两个整数ai aj，表示定居点ai到定居点aj之间有一条缆车路线。1 ≤ n ≤ 2* 105
输出
对每组测试数据，输出一个正整数，表示有多少种不同的仪式方案。
样例输入
1
4
1 4
2 4
3 4
样例输出
6
来源/分类
HNACM2019
题解:
找到以每个点为最大顶点的连接点的数量即可
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
const int maxn=2e5+5;
int n;
vector<int>mp[maxn];
int cnt[maxn];
ll ans[maxn];
int a[maxn];
bool vis[maxn];
ll dfs(int u)
{vis[u]=1;if(cnt[u]==0)return ans[u]=1;if(ans[u])return ans[u];ans[u]=1;for(int i=0;i<mp[u].size();i++){ans[u]+=dfs(mp[u][i]);}return ans[u];
}
ll work(int u)
{ll res=0;for(int i=0;i<mp[u].size();i++){for(int j=i+1;j<mp[u].size();j++){res+=ans[mp[u][i]]*ans[mp[u][j]];}}return res;
}
int main()
{int t;cin>>t;while(t--){for(int i=0;i<maxn;i++){mp[i].clear();vis[i]=cnt[i]=ans[i]=0;}cin>>n;for(int i=0;i<n-1;i++){int x,y;scanf("%d%d",&x,&y);if(x>y){mp[x].push_back(y);cnt[x]++;}else{mp[y].push_back(x);cnt[y]++;}}for(int i=1;i<=n;i++){if(!vis[i]){dfs(i);}}ll sum=0;for(int i=1;i<=n;i++){sum+=work(i);}sum<<=1;cout<<sum<<endl;}return 0;
}
缆车
1612: 缆车
时间限制: 3 Sec 内存限制: 128 MB
提交: 4 解决: 2
[提交] [状态] [讨论版]
题目描述
在远离大陆的太平洋上，有一个风景优美的小岛。传说，小岛上的文明是这样发展起来的。
第一代人沿着岛的坡度选择了n 个定居点，编号为1,2,…,n. 其中编号 i 定居点的高度就是i米。他们在定居点的附近修建了房屋，开辟了农田,种植了植物。
第二代人在 n 个定居点之间修建了n-1条小路，每条小路连接两个定居点，且任意两个定居点之间都可以通过小路相互到达,互通有无。
各个定居点不仅高度不同,而且距离非常远.随着技术的提高,第三代人将盘岛小路改造成可以通缆车的道路。这样不同定居点的人们不费力气就可以借助缆车，自由地到达任何一个定居点。
为了纪念开辟文明的先辈，每年，小岛上都会举行一种特殊的仪式。每年的仪式会选择两个定居点x, y，人们将自己的思念和祝愿写成信件放入缆车，缆车将从定居点x 出发，沿着唯一的路径驶向定居点y。为了体会到翻山越岭的感觉, 岛民们希望缆车行车路线满足如下条件:
缆车依次经过若干定居点a1, a2，…, ak，岛民们认为，如果存在i,在满足 1<i<k 条件下，
a1< a2<……< ai 且 ai >ai+1 ……> ak
a1可以作为出发点，ak 可以作为终止点。
岛民想要知道，存在多少种不同路径的仪式方案？ 所谓两个仪式方案不同，是指在满足约束条件下，如果他们的出发节点不同，或者结束点不同。
输入
第一行： T 表示以下有T组测试数据 （ 1≤ T ≤ 5 ）
对每组数据，第1行： 一个整数n表示定居点个数。 接下来有n-1行，每行两个整数ai aj，表示定居点ai到定居点aj之间有一条缆车路线。1 ≤ n ≤ 2* 105
输出
对每组测试数据，输出一个正整数，表示有多少种不同的仪式方案。
样例输入
1
4
1 4
2 4
3 4
样例输出
6
来源/分类
HNACM2019
题解:
找到以每个点为最大顶点的连接点的数量即可
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
typedef pair<int,int>pii;
typedef long long ll;
const int maxn=2e5+5;
int n;
vector<int>mp[maxn];
int cnt[maxn];
ll ans[maxn];
int a[maxn];
bool vis[maxn];
ll dfs(int u)
{vis[u]=1;if(cnt[u]==0)return ans[u]=1;if(ans[u])return ans[u];ans[u]=1;for(int i=0;i<mp[u].size();i++){ans[u]+=dfs(mp[u][i]);}return ans[u];
}
ll work(int u)
{ll res=0;for(int i=0;i<mp[u].size();i++){for(int j=i+1;j<mp[u].size();j++){res+=ans[mp[u][i]]*ans[mp[u][j]];}}return res;
}
int main()
{int t;cin>>t;while(t--){for(int i=0;i<maxn;i++){mp[i].clear();vis[i]=cnt[i]=ans[i]=0;}cin>>n;for(int i=0;i<n-1;i++){int x,y;scanf("%d%d",&x,&y);if(x>y){mp[x].push_back(y);cnt[x]++;}else{mp[y].push_back(x);cnt[y]++;}}for(int i=1;i<=n;i++){if(!vis[i]){dfs(i);}}ll sum=0;for(int i=1;i<=n;i++){sum+=work(i);}sum<<=1;cout<<sum<<endl;}return 0;
}