合肥网站建设模板系统,wordpress图片主,系部网站建设,网站空间怎么备份对于每个子树#xff0c;直接遍历所有轻儿子#xff0c;继承重儿子 会了板子后#xff0c;修改维护的东西和莫队是一样的
洛谷 U41492
#include bits/stdc.h
#define ll long long
#define ull unsigned long long
constexpr int N1e55;
std::vectorint e…对于每个子树直接遍历所有轻儿子继承重儿子 会了板子后修改维护的东西和莫队是一样的
洛谷 U41492
#include bits/stdc.h
#define ll long long
#define ull unsigned long long
constexpr int N1e55;
std::vectorint e[N];
int c[N],sum[N],ans[N],dfn[N],dfncnt,sz[N],node[N],son[N],tol;void add(int x){if (sum[c[x]]0){tol;}sum[c[x]];
}
void del(int x){sum[c[x]]--;if (sum[c[x]]0){tol--;}
}
void dfs1(int u,int fa){dfn[u]dfncnt;node[dfncnt]u;sz[u]1;int maxson0;for (auto v:e[u]){if (vfa) continue;dfs1(v,u);sz[u]sz[v];if (maxsonsz[v]){son[u]v;maxsonsz[v];}}
}
void dfs2(int u,int fa,bool keep){for (auto v:e[u]){if (vfa||vson[u]) continue;dfs2(v,u,0);}if (son[u]){dfs2(son[u],u,1);}for (auto v:e[u]){if (vfa||vson[u]) continue;for (int idfn[v];idfn[v]sz[v]-1;i){add(node[i]);}}add(u);ans[u]tol;if (!keep){for (int idfn[u];idfn[u]sz[u]-1;i){del(node[i]);}}
}
void yrzr(){int n;std::cinn;for (int i1;in;i){int x,y;std::cinxy;e[x].push_back(y);e[y].push_back(x);}for (int i1;in;i){std::cinc[i];}dfs1(1,0);dfs2(1,0,1);int m;std::cinm;while (m--){int x;std::cinx;std::coutans[x]\n;}
}
int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T1;// std::cinT;while (T--){yrzr();}return 0;
}CF600E 板子改一下修改操作就行了
#include bits/stdc.h
#define ll long long
#define ull unsigned long long
constexpr int N1e55;
std::vectorint e[N];
int c[N],dfn[N],dfncnt,son[N],sz[N],sum[N],node[N],maxn;
ll tol[N],ans[N];
void add(int x){xc[x];tol[sum[x]]-x;sum[x];tol[sum[x]]x;maxnstd::max(maxn,sum[x]);
}
void del(int x){xc[x];tol[sum[x]]-x;sum[x]--;tol[sum[x]]x;if (maxnsum[x]1tol[sum[x]1]0){maxn--;}
}
void dfs1(int u,int fa){dfn[u]dfncnt;node[dfncnt]u;sz[u]1;int maxson0;for (auto v:e[u]){if (vfa) continue;dfs1(v,u);sz[u]sz[v];if (maxsonsz[v]){son[u]v;maxsonsz[v];}}
}
void dfs2(int u,int fa,bool keep){for (auto v:e[u]){if (vfa||vson[u]) continue;dfs2(v,u,0);}if (son[u]){dfs2(son[u],u,1);}for (auto v:e[u]){if (vfa||vson[u]) continue;for (int idfn[v];idfn[v]sz[v]-1;i){add(node[i]);}}add(u);ans[u]tol[maxn];if (!keep){for (int idfn[u];idfn[u]sz[u]-1;i){del(node[i]);}}
}
void yrzr(){int n;std::cinn;for (int i1;in;i){std::cinc[i];}for (int i1;in;i){int x,y;std::cinxy;e[x].push_back(y);e[y].push_back(x);}dfs1(1,0);dfs2(1,0,1);for (int i1;in;i){std::coutans[i] ;}
}
int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T1;// std::cinT;while (T--){yrzr();}return 0;
}
