图论复习
就是一道树剖的裸题 实话说树剖细节挺多的
我打这个代码的时候遗漏的细节
1；有重儿子才先进行重儿子遍历 比如叶节点没有重儿子(默认为0) 是不能遍历的 不然会死循环
2；初始赋值的时候 是对1-n这有序的线段树进行赋值 所以有个rk[] 这个非常易错！！！！ 出题人比较狡诈 样例能过
因为每个节点有个初始id 给出val的时候是有序的 让我们误以为直接赋值线段树就好 但是我们赋值是新的dfs序
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
vectorQ[maxn];
int cnt,n,m;
struct node{
int l,r,maxx,sum;
}tr[maxn<<2];
int val[maxn],dfn[maxn],fa[maxn],top[maxn],sz[maxn],son[maxn],dp[maxn],rk[maxn];
void up(int);
void bd(int,int,int);
int qmax(int,int,int,int,int);
int qsum(int,int,int,int,int);
void upd(int,int,int,int,int);
int Qmax(int,int);
int Qsum(int,int);
void Upd(int,int);
void dfs1(int,int);
void dfs2(int,int);
int main(){
cin>>n;
for(int i=1;i>a>>b;
Q[a].push_back(b);
Q[b].push_back(a);
}
for(int i=1;i<=n;i++)cin>>val[i];
fa[1]=1;
dfs1(1,1);
dfs2(1,1);
bd(1,1,n);
cin>>m;
while(m--){
string s;int a,b;
cin>>s>>a>>b;
if(s=="QMAX")cout<>1;
bd(k<<1,l,mid);
bd(k<<1|1,mid+1,r);
up(k);
}
int qmax(int k,int l,int r,int L,int R){
if(L<=l&&r<=R)return tr[k].maxx;
int mid=l+r>>1;
int res=-1e9;
if(mid>=L)res=max(res,qmax(k<<1,l,mid,L,R));
if(mid>1;
int res=0;
if(mid>=L)res+=qsum(k<<1,l,mid,L,R);
if(mid>1;
if(pos<=mid)upd(k<<1,l,mid,pos,w);
else upd(k<<1|1,mid+1,r,pos,w);
up(k);
}
int Qsum(int u,int v){
int res=0;
while(top[u]!=top[v]){
if(dp[top[u]] 
RMQ上维护最大和次大还是要注意一下的
点击查看代码
#include
#define N 400010
#define M 900010
#define INF 2147483647000000
#define ll long long
using namespace std;
struct edge{
ll u,v,d;
ll next;
}G[N<<1];
ll tot=0;
ll head[N];
inline void addedge(ll u,ll v,ll d)
{
G[++tot].u=u,G[tot].v=v,G[tot].d=d,G[tot].next=head[u],head[u]=tot;
G[++tot].u=v,G[tot].v=u,G[tot].d=d,G[tot].next=head[v],head[v]=tot;
}
ll bz[N][19];
ll maxi[N][19];
ll mini[N][19];
ll deep[N];
inline void dfs(ll u,ll fa)
{
bz[u][0]=fa;
for(ll i=head[u];i;i=G[i].next)
{
ll v=G[i].v;
if(v==fa)continue;
deep[v]=deep[u]+1ll;
maxi[v][0]=G[i].d;
mini[v][0]=-INF;
dfs(v,u);
}
}
ll n;
inline void cal()
{
for(ll i=1;i<=18;++i)
for(ll j=1;j<=n;++j)
{
bz[j][i]=bz[bz[j][i-1]][i-1];
maxi[j][i]=max(maxi[j][i-1],maxi[bz[j][i-1]][i-1]);
mini[j][i]=max(mini[j][i-1],mini[bz[j][i-1]][i-1]);
if(maxi[j][i-1]>maxi[bz[j][i-1]][i-1])mini[j][i]=max(mini[j][i],maxi[bz[j][i-1]][i-1]);
else if(maxi[j][i-1]=0;--i)
if(deep[bz[x][i]]>=deep[y])
x=bz[x][i];
if(x==y)return x;
for(ll i=18;i>=0;--i)
if(bz[x][i]^bz[y][i])
x=bz[x][i],y=bz[y][i];
return bz[x][0];
}
inline ll qmax(ll u,ll v,ll maxx)
{
ll Ans=-INF;
for(ll i=18;i>=0;--i)
{
if(deep[bz[u][i]]>=deep[v])
{
if(maxx!=maxi[u][i])Ans=max(Ans,maxi[u][i]);
else Ans=max(Ans,mini[u][i]);
u=bz[u][i];
}
}
return Ans;
}
inline void read(ll &x)
{
x=0;
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
}
ll m;
edge A[M<<1];
inline bool cmp(edge x,edge y)
{
return x.d 
针对瓶颈生成树 根据其充分性可以直接用最小生成树来解决
