Main » 2013 November 21 » 树链剖分T1—SPOJ DISQUERY
1:49 PM 树链剖分T1—SPOJ DISQUERY |
#include<cstdio> #include<cstdlib> #include<cstring> #include<set> #include<algorithm> #include<map> #include<vector> #include<queue> #include<iostream> #include<string> #include<cmath> #define N 200010 #define lc(x) (x<<1) #define rc(x) ((x<<1)+1) #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; struct Info{int Max,Min;}; struct node{int l,r;Info info;}; int last[N],pre[N],e[N],W[N]; int w[N],pos[N],siz[N],son[N],fa[N],dep[N],top[N],b[N]; Info a[N]; int t1,t2,t3,n,q,len=0,idx=0; void add(int x,int y,int z) {pre[++len]=last[x];last[x]=len;e[len]=y;W[len]=z;} int swap(int &x,int &y){int t=x;x=y;y=t;} Info calc(Info a,Info b) { Info res; res.Min=min(a.Min,b.Min); res.Max=max(a.Max,b.Max); return res; } struct segtree { node tree[4*N]; void update(int x){tree[x].info=calc(tree[lc(x)].info,tree[rc(x)].info);} void build(int x,int L,int R) { tree[x].l=L;tree[x].r=R;int mid=(L+R)>>1; if (L==R) {tree[x].info=a[L];return;} build(lc(x),L,mid);build(rc(x),mid+1,R); update(x); } Info query(int x,int L,int R) { if (tree[x].l==L&&tree[x].r==R) return tree[x].info; int mid=(tree[x].l+tree[x].r)>>1; if (R<=mid) return query(lc(x),L,R); if (L>mid) return query(rc(x),L,R); return calc(query(lc(x),L,mid),query(rc(x),mid+1,R)); } }Tree; void DFS1(int x,int par,int Dep) { dep[x]=Dep;siz[x]=1;son[x]=0; for(int p=last[x];p;p=pre[p]) { int v=e[p]; if (par==v) continue; fa[v]=x;b[v]=W[p]; DFS1(v,x,Dep+1); if (son[x]==0||siz[v]>siz[son[x]]) son[x]=v; siz[x]+=siz[v]; } } void DFS2(int x,int Top) { w[x]=++idx;top[x]=Top; a[idx].Min=a[idx].Max=b[x]; if (son[x]!=0) DFS2(son[x],Top); for(int p=last[x];p;p=pre[p]) { int v=e[p]; if (v==fa[x]||v==son[x]) continue; DFS2(v,v); } } Info getans(int va,int vb) { int f1=top[va],f2=top[vb]; Info tmp;tmp.Max=0;tmp.Min=1e9; while (f1!=f2) { if (dep[f1]<dep[f2]){swap(f1,f2);swap(va,vb);} tmp=calc(tmp,Tree.query(1,w[f1],w[va])); va=fa[f1];f1=top[va]; } if (va==vb) return tmp; if (dep[va]>dep[vb]) swap(va,vb); return calc(tmp,Tree.query(1,w[son[va]],w[vb])); } int main() { scanf("%d",&n);int i; FOR(i,1,n-1) { scanf("%d%d%d",&t1,&t2,&t3); add(t1,t2,t3);add(t2,t1,t3); } DFS1(1,-1,1); DFS2(1,1); Tree.build(1,1,n); scanf("%d",&q); FOR(i,1,q) { scanf("%d%d",&t1,&t2); Info ans=getans(t1,t2); printf("%d %d\n",ans.Min,ans.Max); } }
|
|
|
| Total comments: 0 | |