首页 > 代码库 > 小机房的树——LCA 启蒙题
小机房的树——LCA 启蒙题
大概从一个月前的学考准备阶段就没好好干过什么事，五月底六月初因为要突击文科而削减了奥赛，班主任也说中午暂时别去机房。然后高考放假在家里准备炎德（间断地打了十五盘Dota 2，十五盘是凤凰，输了三盘），本来带了几本文科的资料但是没动。高考完了我们会学校学考。学考完那天下午只有一堂英语，于是我就一个人待在机房，考完回寝室听人说班主任中午说晚上要考试。然后就考试，用十三号和十四号两天的晚自习考了高考卷子（湖南的全国卷乙）。成绩是语文一百，数学九十一，英语一百三十五（其实当时因为时间关系而没有做听力，我是一百零五，但我想我也不至于错高考英语听力，所以就直接给自己加了三十分），理综一百八十六，最后总分五百一十二。虽然还是有诸多不足（尤其数学），但还是大致上了今年湖南一本线。
那几天还是没有奥赛。紧接着后边十七十八期末考试兼分班考试，普通班放假放到二十二号，我们要十九号就返校，年纪部的理由自然是准备炎德。但是当天我到校，就听到我们班有人被“打了电话”，大概内容都是被刷到普通班去了，二十二号再来看分班名单到新的班报道。只有我们三个班陪着准备期末冲刺的高一的那几天还是没有奥赛。二十二号普通班回校，三个班被刷下去十四个人，连大家之前预想的零头都算不上。作为理科第二班，七班下来五个人我们要接着，我们班还要再刷一些下去普通班，最后五十四人。而六班则只走了四个人，据说原先他们（大概说她们更合适）班主任说是要走十五个的。那天全部搬寝室搬教室，普通班要从对楼搬过来高三楼，我们要从一楼搬上三楼。而且我们班的六个老师全换了，因为原先老师里面只有数学老师和七班不一样，他们到高三肯定只能教一个班，而我们的数学老师又要调去高一，所以年纪部干脆全换了。其中只有英语和化学是以前高一的时候教过三班和四班，有些人认识。不过换老师也没有一天到位，因为新的英语和物理老师要带崽，所以这段时间还是原先的老师上课。
二十三号一天炎德考完，上午数学和英语，下午理综，没有语文。考完后又紧接着二十四和二十五两天的上午要数学和化学奥赛初赛，作为培优班的人，就算不是那两个奥赛的人也要强制性地凑个热闹，所以两天上午几乎没上课。到二十六号，才终于算是结束了一切，生活进入（高三）正轨。然而奥赛时间又改了，一个星期六次，每次都是晚上第三四五节晚自习，因为其他奥赛（生物考完了，剩下数理化）到大概八九月就要考完了复赛，现在要冲一冲。咱虽然十一月才考，但是时间得和他们统一。
大概就是这一个月以来的动荡，现在终于安生下来了，学了早就该学的LCA，做了个模板题。
1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 using namespace std; 5 const int N=77777; 6 //Constants;// 7 int n,m; 8 vector<int> gr[N],dis[N],qpnt[N],qnum[N]; 9 //INput;// 10 int fth[N],ans[N]; 11 unsigned long long len[N]; 12 bool vis[N],vt[N]; 13 //Usage;// 14 int fnd(int x){ 15 return (fth[x]==x?x:fnd(fth[x])); 16 } 17 void uni(int x,int y){ 18 int tmp=fnd(y); 19 if(tmp!=x)fth[tmp]=x; 20 } 21 void dfs(int x,unsigned long long d){ 22 len[x]=d; 23 for(int i=0;i<gr[x].size();i++) 24 if(!vt[gr[x][i]]){ 25 vt[gr[x][i]]=true; 26 dfs(gr[x][i],d+dis[x][i]); 27 uni(x,gr[x][i]); 28 } 29 vis[x]=true; 30 for(int i=0;i<qpnt[x].size();i++) 31 if(vis[qpnt[x][i]]) 32 ans[qnum[x][i]]=len[qpnt[x][i]]+len[x]-2*len[fnd(qpnt[x][i])]; 33 } 34 //Function(s);// 35 int main(){ 36 for(int i=1;i<N;i++)fth[i]=i; 37 //Pre-INput;// 38 cin>>n; 39 for(int i=1;i<n;i++){ 40 int x,y,z;cin>>x>>y>>z; 41 gr[x].push_back(y);dis[x].push_back(z); 42 gr[y].push_back(x);dis[y].push_back(z); 43 } 44 cin>>m; 45 for(int i=1;i<=m;i++){ 46 int x,y;cin>>x>>y; 47 qpnt[x].push_back(y);qnum[x].push_back(i); 48 qpnt[y].push_back(x);qnum[y].push_back(i); 49 } 50 //INput;// 51 vt[0]=true; 52 dfs(0,0); 53 //Calculating;// 54 for(int i=1;i<=m;i++)cout<<ans[i]<<endl; 55 //OUTput;// 56 return 0; 57 }
耗时是codevs 上1273ms。
小机房的树——LCA 启蒙题