模板汇总
2026-04-04 20:06:44
发布于：广东
16阅读
0回复
0点赞
一、树状数组
struct BIT{
ll n;
vector<ll> tr;
BIT(){}
BIT(ll len){
init(len);
}
void init(ll len){
n=len;
tr.resize(n+1);
}
ll lowbit(ll x){
return x&-x;
}
void add(ll x,ll d){
for(;x<=n;x+=lowbit(x))
tr[x]+=d;
}
ll ask(ll x){
ll res=0;
for(;x>=1;x-=lowbit(x))
res+=tr[x];
return res;
}
ll sum(ll x,ll y){
return ask(y)-ask(x-1);
}
};
二、建图
struct GRA{
ll n;
vector<vector<ll>> gr;
GRA(){}
GRA(ll len){
init(len);
}
void init(ll len){
n=len;
gr.resize(n+1);
}
void add(ll x,ll y){
gr[x].push_back(y);
gr[y].push_back(x);
}
};
三、树的重心
struct TZX{
ll n;
GRA g;
vector<ll> sz,w,pr,ans;
TZX(){}
TZX(ll len){
n=len;
g.init(len);
sz.resize(n+1);
w.resize(n+1);
pr.resize(n+1);
}
void ins(){
for(ll i=1;i<n;i++){
ll u,v;
cin>>u>>v;
g.add(u,v);
}
}
void dfs(ll x,ll p){
sz[x]=1;
pr[x]=p;
for(ll s:g.gr[x]){
if(s==p)
continue;
dfs(s,x);
sz[x]+=sz[s];
w[x]=max(w[x],sz[s]);
}
w[x]=max(w[x],n-sz[x]);
}
void gas(){
dfs(1,0);
ll mn=INF;
for(ll i=1;i<=n;i++)
mn=min(mn,w[i]);
for(ll i=1;i<=n;i++)
if(w[i]==mn)
ans.push_back(i);
}
};
还有待更新……
全部评论 3
我和“穿越时空ℜ”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1988761617416822784
2026-04-04 来自 浙江
0
有帮助，赞一个