最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

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

CF競(jìng)賽題目講解_Tree Requests(樹上啟發(fā)式合并)

2022-05-19 11:00 作者:Clayton_Zhou  | 我要投稿


// https://codeforces.com/problemset/problem/570/D

?

#include "stdafx.h"

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


#include <algorithm>?

#include <vector>?

using namespace std;


#define ll long long

#define pii pair<int, int>

const int maxn = 5e5 + 10;


//1為根 有根樹 帶點(diǎn)權(quán) 點(diǎn)權(quán)a到z 詢問rt子樹 深度為d的這層節(jié)點(diǎn) 點(diǎn)權(quán)重排能否構(gòu)成回文串

?

//暴力 -> 樹上啟發(fā)式合并

vector<int> g[maxn];

int cnt[maxn][30];//深度為i 字母為j的個(gè)數(shù)

int son[maxn],siz[maxn],dep[maxn];

char col[maxn]="\0zacccd";

vector<pii> q[maxn];

bool ans[maxn];


int L[maxn],V[maxn],T=0;//? dfs 順序編號(hào)


//輕重鏈剖分

void dfs(int rt)?

{

siz[rt]=1;

V[L[rt]=++T]=rt;

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

{

dep[i]=dep[rt]+1;

dfs(i);

if(siz[i] > siz[son[rt]]) son[rt]=i;

siz[rt]+=siz[i];

}

}

bool check(int d) //check深度為d? 字母分布情況

{

int odd=0;//奇數(shù)個(gè)數(shù)

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

{

odd+=(cnt[d][i]&1);

}

return odd<=1;

}



void dfs2(int rt,bool ok)?

{

for(auto i:g[rt])?

{

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

dfs2(i,0);

}

if(son[rt]) dfs2(son[rt],1);


for(auto k:g[rt])?

{

if(k==son[rt]) continue;

for (int i=0; i<siz[k]; i++)?

{

int id=col[V[L[k]+i]]-'a'+1;

cnt[dep[V[L[k]+i]]][id]+=1;

}

}

int id=col[rt]-'a'+1;

cnt[dep[rt]][id]+=1;

for(auto i:q[rt])?

{? ?//? i.second 為查詢標(biāo)號(hào), i.first 為查詢深度

ans[i.second]=check(i.first);

}?

if(!ok) //是輕兒子 clear

for (int i=0; i<siz[rt]; i++)?

{

id=col[V[L[rt]+i]]-'a'+1;

cnt[dep[V[L[rt]+i]]][id]-=1;

}

}

int n,m;

int main()

{

n=6,m=5;

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


int fa;

int faa[8]={1 ,1, 1, 3 ,3};

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

{

//int fa;scanf("%d",&fa);

fa=faa[i-2];

g[fa].push_back(i);

}


//scanf("%s",col+1);

dep[1]=1;

dfs(1);


int qq[32][2]={

1 ,1,

3 ,3,

4, 1,

6, 1,

1, 2};

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

{

int u,d;

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

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

d=qq[i-1][1];

q[u].push_back(make_pair (d,i));

}

dfs2(1,1);

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

if(ans[i]) puts("Yes");

else puts("No");

return 0;

}


CF競(jìng)賽題目講解_Tree Requests(樹上啟發(fā)式合并)的評(píng)論 (共 條)

分享到微博請(qǐng)遵守國家法律
广饶县| 深泽县| 双城市| 炉霍县| 金湖县| 松江区| 盐山县| 莎车县| 美姑县| 芦山县| 永新县| 密云县| 色达县| 石景山区| 洛川县| 雅安市| 威宁| 名山县| 临泉县| 离岛区| 高州市| 岢岚县| 遂宁市| 黑龙江省| 乡城县| 汉阴县| 建阳市| 山阳县| 澜沧| 浦东新区| 海原县| 友谊县| 扶余县| 海南省| 东乌| 林甸县| 神农架林区| 龙南县| 息烽县| 浠水县| 平昌县|