1787: [Ahoi2008]Meet 紧急集合
2013年3月25日 14:53
http://www.lydsy.com/JudgeOnline/problem.php?id=1787
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 375404 | Liu_Ts | 1787 | Accepted | 45732 kb | 7584 ms | C++ | 2039 B | 2013-03-25 11:25:27 |
题意
一棵树，每次询问给三个点，求一个点使得到这三个点的距离和最小。
题解
理解一下，可知答案必定在这三个点中，某两个点的LCA上，
于是枚举a,b;a,c;b,c的LCA。
最后发现这三个LCA有规律，有两个一定相同，但是不会用。
LCA写的RMQ比较慢啊
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include<cstring>#include<climits>#include<cmath>#include<cstdio>#include<algorithm>using namespace std;const int N=500001,M=1000001,Q=2000002;int q[Q],d[N],tot,n,k,v[M],next[M],head[N],num[N],m;struct SegmentTree{ int m[6000002]; void update(int x) { int l=x<<1,r=l+1; m[x]=m[l]; if(d[m[x]]>d[m[r]]) m[x]=m[r]; } void build(int x,int s,int t) { if(s==t) { m[x]=q[s];return; } int mid=s+t>>1; build(x<<1,s,mid);build((x<<1)+1,mid+1,t); update(x); } int get(int x,int s,int t,int ll,int rr) { if(ll<=s&&t<=rr) return m[x]; int t1=0,t2=0,mid=s+t>>1; if(ll<=mid) t1=get(x<<1,s,mid,ll,rr); if(rr>mid) t2=get((x<<1)+1,mid+1,t,ll,rr); if(d[t1]<d[t2]) return t1; else return t2; }}a;void add(int x,int y){ v[++k]=y;next[k]=head[x];head[x]=k;}void dfs(int x,int fa,int deep){ q[++q[0]]=x;num[x]=q[0];d[x]=deep; for(int i=head[x];i;i=next[i]) if(v[i]!=fa) dfs(v[i],x,deep+1),q[++q[0]]=x;}int lca(int x,int y){ if(num[x]>num[y]) swap(x,y); return a.get(1,1,q[0],num[x],num[y]); }int main(){ scanf("%d%d",&n,&m);int x,y,z; for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); add(x,y);add(y,x); } dfs(1,0,0);d[0]=INT_MAX; a.build(1,1,q[0]); int p,q; while(m--) { int ans,sum=INT_MAX; scanf("%d%d%d",&x,&y,&z); int s=d[x]+d[y]+d[z]; p=lca(x,y);q=lca(p,z); if(s-d[q]*2-d[p]<sum) sum=s-d[q]*2-d[p],ans=p; p=lca(x,z); if(s-d[q]*2-d[p]<sum) sum=s-d[q]*2-d[p],ans=p; p=lca(y,z); if(s-d[q]*2-d[p]<sum) sum=s-d[q]*2-d[p],ans=p; printf("%d %d\n",ans,sum); }} |
