宁波网站建设优化企业推荐,品牌推广内容,网页设计与制作教程电,外网专线AGC023F - 01 on Tree
题目描述
Solution
有一个奇妙的贪心思路。#xff08;奇妙的原因是我不会证#xff09; 这一题的结点需要按拓扑序排序#xff0c;并让逆序对个数最小。 考虑在儿子向父亲合并的过程中统计答案#xff0c;产生的逆序对个数就是cnt[father][1]∗cn…AGC023F - 01 on Tree
题目描述
Solution
有一个奇妙的贪心思路。奇妙的原因是我不会证 这一题的结点需要按拓扑序排序并让逆序对个数最小。 考虑在儿子向父亲合并的过程中统计答案产生的逆序对个数就是cnt[father][1]∗cnt[son][0]cnt[father][1]*cnt[son][0]cnt[father][1]∗cnt[son][0]其中cnt[x][0/1]cnt[x][0/1]cnt[x][0/1]表示xxx这个联通块已经拥有的0/10/10/1结点的数量我们贪心地选取cnt[x][0]cnt[x][1]\frac{cnt[x][0]}{cnt[x][1]}cnt[x][1]cnt[x][0]最小的结点合并到父亲并堆维护这一过程就可以做到O(nlgn)O(nlgn)O(nlgn)求解答案。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
int cnt[MAXN][2],fa[MAXN],f[MAXN];
struct heapnode
{int x,y,id;bool operator (const heapnode a) const { return 1ll*x*a.y1ll*y*a.x; }
};
priority_queueheapnode heap;
int find(int x){ return f[x]x?f[x]:f[x]find(f[x]); }
int main()
{int nread();for (int i2;in;i) fa[i]read();for (int i1;in;i) {int xread();cnt[i][x];f[i]i;}for (int i2;in;i) heap.push((heapnode){cnt[i][0],cnt[i][1],i});ll ans0;while (!heap.empty()){int ufind(heap.top().id),xheap.top().x,yheap.top().y; heap.pop();if (cnt[u][0]xcnt[u][1]y){int vfind(fa[u]);ans1ll*cnt[v][1]*cnt[u][0];cnt[v][0]cnt[u][0];cnt[v][1]cnt[u][1];f[u]v;if (v!1) heap.push((heapnode){cnt[v][0],cnt[v][1],v});}}printf(%lld\n,ans);return 0;
}
