NC219740. 学霸大帅哥zyh
描述
众所周知，学霸大帅哥zyh的迷妹是非常多的。 迷妹经常因为抢夺zyh而发生争吵，产生了了不同的派系，每个派系有自己的编号。假设每个城市中只有一个派系。 有n座城市通过n-1条道路连接成一个联通块（简单来说就是一颗树）。zyh为了守护城市的和平与安宁，不得不出游来安抚迷妹的心。 为了照顾所有派系的迷妹，zyh每次游行都会走完n-1条边（不考虑走的顺序和路径）。 为了和迷妹们互动，在每条道路上，zyh会选择道路两边出现公共次数最多的迷妹派系编号的旗子举在手中。 若两边公共出现最多的数量为0，则zyh会选择偷懒，不举旗子。若存在两个及以上最大公共出现次数相同的情况，则会举编号最大的旗子。 （道路两边的意思是，zyh在某条树边的时候，假设此时树边断开（并不会真正断开），那么会产生两个联通块，我们称为道路两边。 公共出现的意思是，假设一个联通块有1，2，2，3，另一个联通块里有2，2，2，3，3。那么1公共出现0次， 2公共出现2次，3公共出现1次。 所以此时zyh会举编号为2的旗子）。
输入描述
第一行为n(1<=n<=1e5)。代表n个城市。第二行输入n个城市的迷妹派系编号ai(1<=ai<=1e5)。接下来n–1行，代表n−1条树边，每行包含两个整数ui,vi,(1<=ui,vi<=n)。代表ui和vi相连通。
输出描述
共n−1行，代表zyh经过这条树边时会举哪个编号的旗子，若不举旗子，则输出−1。输出边的顺序与输入边的顺序相同。
示例1
输入:
3 2 1 2 1 2 1 3
输出:
-1 2
说明:
示例2
输入:
7 1 2 3 2 2 3 3 1 2 1 3 2 4 2 5 3 6 3 7
输出:
-1 -1 2 2 3 3
C++ 解法, 执行用时: 405ms, 内存消耗: 66504K, 提交时间: 2022-04-19 11:55:20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const int N=1e5+5;
vector<pii>g[N];
map<int,int>mp[N];
int cnt[N],a[N],ans[N];
void dfs(int x,int last){
for (auto v:g[x]){
if (v.first!=last){
dfs(v.first,x);
int mx=1,col=-1;
for (auto c:mp[v.first]) {
int temp=min(cnt[c.first]-c.second,c.second);
if (temp>=mx){
mx=temp;
col=c.first;
}
mp[x][c.first]+=c.second;
}
ans[v.second]=col;
}
}
mp[x][a[x]]++;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
for (int i=1;i<=n;i++) {
cin>>a[i];
cnt[a[i]]++;
}
for (int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
g[u].push_back({v,i});
g[v].push_back({u,i});
}
dfs(1,0);
for (int i=1;i<n;i++) cout<<ans[i]<<"\n";
return 0;
}