给一棵树，维护上面两点最短路径中结点的最大值及最大值出现次数
#include <stdio.h> #include<string.h> #include<algorithm> using namespace std; const int maxn = 300010+10; #define inf 1000000005 typedef pair<int,int>pii; int w[maxn]; int N, Q; struct { int to,next,w; }e[maxn<<2]; int head[maxn<<1],edgeNum; struct { int u,v; }edge[maxn<<1]; void add(int u,int v) { e[edgeNum].next = head[u]; e[edgeNum].to = v; // e[edgeNum].w=w; head[u] = edgeNum++; } /*-------------------------树剖------------------------------*/ int deep[maxn],fa[maxn],siz[maxn],son[maxn]; void dfs1(int u,int pre,int d) { deep[u] = d; fa[u] = pre; siz[u] = 1; son[u] = 0; for(int i=head[u];~i;i=e[i].next) { int v = e[i].to; if(v!=pre) { dfs1(v,u,d+1); siz[u] += siz[v]; if(siz[v]>siz[son[u]]) son[u] = v; } } } int top[maxn],id[maxn],rk[maxn],cnt; void dfs2(int u,int t) { top[u] = t; id[u] = ++cnt; rk[cnt] = u; if(!son[u]) return; dfs2(son[u],t); for(int i=head[u];~i;i=e[i].next) { int v = e[i].to; if(v!=son[u]&&v!=fa[u]) dfs2(v,v); } } /*-------------------------树剖------------------------------*/ /*-------------------------线段树------------------------------*/ #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 int sum[maxn<<2],maxv[maxn<<2],lazy[maxn<<2],ci[maxn<<2]; void pushup(int rt) { if(maxv[rt<<1]>maxv[rt<<1|1]){ sum[rt]=sum[rt<<1]; } else if(maxv[rt<<1]<maxv[rt<<1|1])sum[rt]=sum[rt<<1|1]; else sum[rt] = (sum[rt<<1] + sum[rt<<1|1]); maxv[rt] =max(maxv[rt<<1],maxv[rt<<1|1]); } void change(int val,int q,int l,int r,int rt)//单点更新 { if(l==r) { sum[rt]=1;//出现次数 maxv[rt]=val; return ; } int m = l + r >> 1; if(q<=m) change(val,q,lson); else change(val,q,rson); pushup(rt); } pii query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return {maxv[rt],sum[rt]}; int m = l + r >> 1; pii a={0,0},b={0,0},ans; if (L<=m)a=query(L,R,lson); if (R>m)b=query(L,R,rson); if(a.first==b.first)ans={a.first,a.second+b.second}; else if(a.first<b.first)ans=b; else ans=a; return ans; } int querymax(int L,int R,int l,int r,int rt){ if (L<=l&&r<=R)return maxv[rt]; int m=(l+r)>>1,ans=-inf;//注意负数① if (L<=m)ans=max(ans,querymax(L,R,lson)); if (R>m)ans=max(ans,querymax(L,R,rson)); //pushup(rt); return ans; } /*-------------------------线段树------------------------------*/ /*-----------------------树剖加线段树--------------------------*/ pii query(int x,int y) { pii ans = {-2,-2}; while(top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x,y); pii tmp = query(id[top[x]],id[x],1,cnt,1); if(tmp.first==ans.first)ans={tmp.first,tmp.second+ans.second}; else if(tmp.first>ans.first)ans=tmp; x = fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); pii tmp = query(id[x],id[y],1,cnt,1); if(tmp.first==ans.first)ans={tmp.first,tmp.second+ans.second}; else if(tmp.first>ans.first)ans=tmp; return ans; } int querymax(int x,int y) { int ans =-inf;//注意负数② while(top[x] != top[y]) { if(deep[top[x]] < deep[top[y]]) swap(x,y); ans = max(ans ,querymax(id[top[x]],id[x],1,cnt,1)); x = fa[top[x]]; } if(deep[x]>deep[y]) swap(x,y); ans = max(ans ,querymax(id[x],id[y],1,cnt,1)); return ans; } /*-----------------------树剖加线段树--------------------------*/ void init() { memset(head,-1,4*N+4); cnt = edgeNum = 0; } int u, v, o,z,cur; int main() { scanf("%d",&N); init(); for(int i=1;i<=N;i++)scanf("%d",&w[i]); for(int i=1;i<N;++i) { //w[i] = 0; scanf("%d%d",&u,&v); // edge[i].u=u,edge[i].v=v;//真正的边数 add(u,v);//边数*2 add(v,u); } dfs1(1,0,1); dfs2(1,1); for(int i=1;i<=N;i++){ change(w[i],id[i],1,N,1); } scanf("%d",&Q); // build(1,cnt,1); while(Q--) { scanf("%d%d",&o,&z); pii res=query(o,z); printf("%d %d\n",res.first,res.second); } return 0; }感谢睿明锅，lca做法待更
