本文主要是介绍CSU 2172 买一送一，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：点击打开链接
题意：略。
题解：首先要看出来这是一棵树，然后就想怎么去重
设当前节点为u，商品类型为a[u]，父节点为fa
在dfs的过程中维护这几个信息：
1、 上一个以a[u]为第二分量的二元对的数目pre[a[u]]
2、 从根到fa的不同商品类型的数目num，即以当前a[u]为第二分量的二元对的数目
3、 从根到fa的答案ans[fa]
那么当前的答案就是ans[u]=ans[fa]+num-pre[a[u]]
时间复杂度O(n)。
注意会爆int，要使用long long！
代码：
#include<bits/stdc++.h>
using namespace std;
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define pb push_back
const int N = 1e5+10;int n,a[N],ct[N],hs[N],cnt;
long long ans[N];///注意使用long long 极端情况1e5*1e5
vector<int> e[N],v[N];void dfs(int fa) {for(int i=0;i<e[fa].size();i++) {int x=e[fa][i];if(!hs[a[fa]]) cnt++;hs[a[fa]]++;ans[x]=ans[fa]+cnt-ct[a[x]];v[a[x]].pb(cnt);ct[a[x]]=cnt;dfs(x);hs[a[fa]]--;if(hs[a[fa]]==0) cnt--;v[a[x]].pop_back();ct[a[x]]=v[a[x]][v[a[x]].size()-1];}
}int main() {while(scanf("%d",&n)!=EOF) {int x;rep(i,2,n) scanf("%d",&x),e[x].pb(i);rep(i,1,n) scanf("%d",&a[i]);///初始化 prerep(i,1,n) v[i].pb(0);///到n就行了 防止mle 和 tledfs(1);rep(i,2,n) printf("%lld\n",ans[i]);rep(i,1,n) e[i].clear(),v[i].clear();mst(ct,0),mst(hs,0),cnt=0;}return 0;
}
这篇关于CSU 2172 买一送一的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
