怎样做美食网站,wordpress单号管理系统,网页设计实训报告工作内容和步骤,seo软件系统正题
题目链接:https://www.luogu.com.cn/problem/AT3957 题目大意 nnn个节点的一棵树#xff0c;每个节点有0/10/10/1。每次删除一个根节点#xff0c;然后把该节点的值填入序列#xff0c;求最终序列的最小逆序对数量。 n≤2105n\leq 2\times 10^5n≤2105 解题思路
考虑…正题
题目链接:https://www.luogu.com.cn/problem/AT3957 题目大意
nnn个节点的一棵树每个节点有0/10/10/1。每次删除一个根节点然后把该节点的值填入序列求最终序列的最小逆序对数量。
n≤2×105n\leq 2\times 10^5n≤2×105 解题思路
考虑一种贪心开始每个节点作为一个单独的联通块每次选择一个节点把它和它父节点的联通快合并并且它的联通快排在它父节点的后面。
显然这样的选择可以构成所有可能的序列现在需要考虑选择顺序。设cntx,0/1cnt_{x,0/1}cntx,0/1表示联通块xxx的0/10/10/1数量。
那么一个节点的两个子节点两个联通块x,yx,yx,y的顺序xxx排在yyy前面就会产生cntx,1×cnty,0cnt_{x,1}\times cnt_{y,0}cntx,1×cnty,0的贡献所以如果xxx排在yyy前面那么有 cntx,1×cnty,0≤cnty,1×cntx,0cnt_{x,1}\times cnt_{y,0}\leq cnt_{y,1}\times cnt_{x,0}cntx,1×cnty,0≤cnty,1×cntx,0 化一下就是按照cntx,1cntx,0\frac{cnt_{x,1}}{cnt_{x,0}}cntx,0cntx,1从小到大选就好了。维护一个堆即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N2e510;
int n,f[N],fa[N],cnt[N][2];
long long ans;
struct node{int x,w0,w1;node(int xx0){xxx;w0cnt[xx][0];w1cnt[xx][1];return;}
};
bool operator(node x,node y)
{return 1ll*x.w1*y.w01ll*x.w0*y.w1;}
priority_queuenode q;
int find(int x)
{return (fa[x]x)?x:(fa[x]find(fa[x]));}
int main()
{scanf(%d,n);for(int i2;in;i)scanf(%d,f[i]);for(int i1;in;i){int x;scanf(%d,x);cnt[i][x];fa[i]i;if(i1)q.push(node(i));}while(!q.empty()){node wq.top();q.pop();int xfind(w.x);if(fa[x]!x)continue;if(cnt[x][0]!w.w0)continue;if(cnt[x][1]!w.w1)continue;int yfind(f[x]);fa[x]y;ans1ll*cnt[y][1]*cnt[x][0];cnt[y][0]cnt[x][0];cnt[y][1]cnt[x][1];if(y)q.push(node(y));}printf(%lld\n,ans);return 0;
}
