国产精品天干天干,亚洲毛片在线,日韩gay小鲜肉啪啪18禁,女同Gay自慰喷水

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

CF競賽題目講解_CF600E(樹上啟發(fā)式合并)

2022-05-21 10:28 作者:Clayton_Zhou  | 我要投稿

// https://codeforces.com/problemset/problem/600/E

//? 與下題類似,?DongDong詢問以x為根的子樹中有多少種不同的顏色.

// https://ac.nowcoder.com/acm/contest/31084/C


#include "stdafx.h"

//#include <bits/stdc++.h>

#include<cstdio>

#include<cstring>

#include<iostream>

#include <algorithm>?

#include <vector>?

//#include<bits/stdc++.h>

using namespace std;

?

const int maxn = 1e5 + 10;?


//給定樹 帶點(diǎn)權(quán) 詢問子樹中,出現(xiàn)次數(shù)最多的若干種點(diǎn)權(quán)的點(diǎn)權(quán)和 (顏色值之和)

//暴力解法 對于每個(gè)子樹都花O(n)求出其答案,并用O(N)清空影響? 時(shí)間O(N平方)

//發(fā)現(xiàn)對于根節(jié)點(diǎn)rt,最后遞歸的子樹可以不刪,保留信息給根節(jié)點(diǎn),我們最后遞歸重兒子,保留重兒子的信息 即:啟發(fā)式合并

//我們保留重兒子,刪除輕兒子的影響,并最后重新統(tǒng)計(jì)一遍輕兒子

// 某個(gè)點(diǎn)u被訪問:要么通過重鏈(不會被刪,只會被訪問1次),要么通過輕邊,但根到u一般logn條輕邊,所以 總復(fù)雜度nlogn

vector<int> g[maxn];

int v[maxn]={0,

1 ,2, 3, 4

};

int cnt[maxn];

int mmx;//眾數(shù)出現(xiàn)次數(shù)

long long ret, ans[maxn];

int n;

//輕重鏈剖分

int son[maxn],siz[maxn];

int L[maxn],R[maxn],V[maxn],cur;


void dfs(int rt,int fa) //dfs預(yù)處理樹上信息

{

siz[rt]=1;// 子樹大小

V[L[rt] = cur++] = rt;// 子樹dfs編號

for(int &i:g[rt])?

{

if(i==fa) continue;

dfs(i,rt);

if(siz[i] > siz[son[rt]]) son[rt]=i;// 求重兒子

siz[rt]+=siz[i];

}

R[rt]=cur;//? 子樹dfs編號結(jié)束位置??

}

?

void add(int rt )// 統(tǒng)計(jì)rt貢獻(xiàn)??

{

cnt[v[rt]]+=1;

if(cnt[v[rt]]==mmx) // 多種顏色同時(shí)出現(xiàn)次數(shù)最多

{

ret+=v[rt];// 累加顏色值

}

else if(cnt[v[rt]] > mmx) // 一種顏色出現(xiàn)次數(shù)最多

{

mmx=cnt[v[rt]];

ret=v[rt];// 重新賦值顏色值

}

//if(rt==2)

{

cout<<"rt="<<rt<<", mmx="<<mmx<<",? "<<cnt[v[rt]]<<",? "<<ret<<endl;

}

}


?

void dfs2(int rt,int fa,bool ok) //先遞歸輕鏈 最后再求重兒子. 求父節(jié)點(diǎn)的答案繼承重兒子的信息, 再暴力統(tǒng)計(jì)輕兒子

{

for(int &i:g[rt])?

{

if(i==fa || i==son[rt]) continue;

dfs2(i,rt,0);

}

if(son[rt]) dfs2(son[rt],rt,1);//重鏈的信息 不會被刪


add(rt); //統(tǒng)計(jì)根

for(int &i:g[rt]) //暴力統(tǒng)計(jì)輕兒子

{

if(i==fa || i==son[rt]) continue;

for (int k=L[i]; k<R[i]; k++) add(V[k]); ?

}

?

ans[rt]=ret;

if(!ok) //? ?刪去整棵輕兒子子樹的信息

{

for (int k=L[rt]; k<R[rt]; k++) cnt[v[V[k]]]--;?

mmx=-1;

ret=0;

}

}

int edge[32][2]={

1, 2,

2, 3,

2 ,4

};

int main()

{

n=4;

//scanf("%d",&n);

// for(int i=1;i<=n;i++) scanf("%d",v+i);

for(int i=1;i<n;i++)?

{

int v,u;

//scanf("%d %d",&u,&v);

u=edge[i-1][0];

v=edge[i-1][1];

g[u].push_back(v);

g[v].push_back(u);

}

dfs(1,0);

dfs2(1,0,1);

for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];

return 0;

}


CF競賽題目講解_CF600E(樹上啟發(fā)式合并)的評論 (共 條)

分享到微博請遵守國家法律
宁乡县| 呈贡县| 玛多县| 北碚区| 清河县| 监利县| 安塞县| 岢岚县| 郁南县| 华池县| 满城县| 南通市| 望奎县| 清流县| 洛宁县| 清丰县| 巴塘县| 沙雅县| 新竹县| 冀州市| 安新县| 维西| 涞水县| 浦江县| 朝阳县| 河津市| 铁岭市| 昔阳县| 吉木萨尔县| 吉林市| 宁武县| 温泉县| 略阳县| 邵阳市| 随州市| 淳安县| 石林| 和静县| 泸西县| 永修县| 东光县|