日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國(guó)內(nèi)最全I(xiàn)T社區(qū)平臺(tái) 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置：首頁(yè) > php開(kāi)源 > php教程 > Codefources 519E. A and B and Lecture Rooms LCA

Codefources 519E. A and B and Lecture Rooms LCA

來(lái)源：程序員人生   發(fā)布時(shí)間：2015-03-14 09:51:45 閱讀次數(shù)：3237次


簡(jiǎn)單LCA:

求樹(shù)上距離給定兩個(gè)點(diǎn)a,b距離相等的點(diǎn)有多少個(gè)

先預(yù)處理出每一個(gè)節(jié)點(diǎn)的孩子個(gè)數(shù)sum[x],求出a,b的LCA,根據(jù)深度就能夠知道兩個(gè)點(diǎn)的距離,距離為偶數(shù)的有解.... 

根據(jù)lca在a,b之間的位置不同分情況討論:

設(shè)a與lca距離為 ha , b與lca距離為 hb 

1:lca在a,b正中間既a,b分別屬于lca的兩個(gè)子樹(shù)中, 結(jié)果為: n-sum[ a往上距離lca ha⑴ 的點(diǎn)] - sum[ b往上距離lca hb⑴ 的點(diǎn)] 

2:a,b兩個(gè)點(diǎn)相對(duì)lca1上1下. c:a,b中靠下的那個(gè)點(diǎn) 結(jié)果為: sum[lca]-sum[ c往上距離lca hc⑴ 的點(diǎn) ]


用倍增法求LCA  O(logn) , 總時(shí)間復(fù)雜度 O(mlogn) 



E. A and B and Lecture Rooms
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A and B are preparing themselves for programming contests.

The University where A and B study is a set of rooms connected by corridors. Overall, the University has n rooms connected by n?-?1corridors so that you can get from any room to any other one by moving along the corridors. The rooms are numbered from 1 to n.

Every day А and B write contests in some rooms of their university, and after each contest they gather together in the same room and discuss problems. A and B want the distance from the rooms where problems are discussed to the rooms where contests are written to be equal. The distance between two rooms is the number of edges on the shortest path between them.

As they write contests in new rooms every day, they asked you to help them find the number of possible rooms to discuss problems for each of the following m days.

Input

The first line contains integer n (1?≤?n?≤?105) ― the number of rooms in the University.

The next n?-?1 lines describe the corridors. The i-th of these lines (1?≤?i?≤?n?-?1) contains two integers ai and bi (1?≤?ai,?bi?≤?n), showing that the i-th corridor connects rooms ai and bi.

The next line contains integer m (1?≤?m?≤?105) ― the number of queries.

Next m lines describe the queries. The j-th of these lines (1?≤?j?≤?m) contains two integers xj and yj (1?≤?xj,?yj?≤?n) that means that on thej-th day A will write the contest in the room xj, B will write in the room yj.

Output

In the i-th (1?≤?i?≤?m) line print the number of rooms that are equidistant from the rooms where A and B write contest on the i-th day.

Sample test(s)
input
4 1 2 1 3 2 4 1 2 3
output
1
input
4 1 2 2 3 2 4 2 1 2 1 3
output
0 2
Note

in the first sample there is only one room at the same distance from rooms number 2 and 3 ― room number 1.



/* *********************************************** Author :CKboss Created Time :2015年03月05日 星期4 16時(shí)52分05秒 File Name :E.cpp ************************************************ */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <string> #include <cmath> #include <cstdlib> #include <vector> #include <queue> #include <set> #include <map> using namespace std; const int maxn=100100; const int DEG=20; struct Edge { int to,next; }edge[maxn*2]; int Adj[maxn],Size; void init_edge() { memset(Adj,⑴,sizeof(Adj)); Size=0; } void Add_Edge(int u,int v) { edge[Size].to=v; edge[Size].next=Adj[u]; Adj[u]=Size++; } int fa[maxn][DEG]; int deg[maxn]; void BFS(int root) { queue<int> q; deg[root]=0; fa[root][0]=root; q.push(root); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=1;i<DEG;i++) fa[u][i]=fa[fa[u][i⑴]][i⑴]; for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(v==fa[u][0]) continue; deg[v]=deg[u]+1; fa[v][0]=u; q.push(v); } } } int LCA(int u,int v) { if(deg[u]>deg[v]) swap(u,v); int hu=deg[u],hv=deg[v]; int tv=v,tu=u; for(int det=hv-hu,i=0;det;i++,det=det/2) if(det&1) tv=fa[tv][i]; if(tv==tu) return tu; for(int i=DEG⑴;i>=0;i--) { if(fa[tu][i]==fa[tv][i]) continue; tu=fa[tu][i]; tv=fa[tv][i]; } return fa[tu][0]; } int n,m; int sum[maxn]; int DFS(int u) { int ret=1; for(int i=Adj[u];~i;i=edge[i].next) { int v=edge[i].to; if(v==fa[u][0]) continue; ret+=DFS(v); } return sum[u]=ret; } void solve(int x,int y) { if(x==y) { printf("%d ",n); return ; } int lca=LCA(x,y); int h1=deg[x]-deg[lca]; int h2=deg[y]-deg[lca]; if((h1+h2)%2==1) { puts("0"); return ; } if(h1==h2) { int p1=x,p2=y; for(int det=(h1+h2)/2⑴,i=0;det;i++,det/=2) if(det&1) p1=fa[p1][i]; for(int det=(h1+h2)/2⑴,i=0;det;i++,det/=2) if(det&1) p2=fa[p2][i]; printf("%d ",n-sum[p1]-sum[p2]); } else { if(deg[x]<deg[y]) swap(x,y); int p1=x,p2=x; for(int det=(h1+h2)/2,i=0;det;i++,det/=2) if(det&1) p1=fa[p1][i]; for(int det=(h1+h2)/2⑴,i=0;det;i++,det/=2) if(det&1) p2=fa[p2][i]; int ans=sum[p1]-sum[p2]; printf("%d ",ans); } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); init_edge(); scanf("%d",&n); for(int i=0;i<n⑴;i++) { int a,b; scanf("%d%d",&a,&b); Add_Edge(a,b); Add_Edge(b,a); } BFS(1); DFS(1); scanf("%d",&m); while(m--) { int a,b; scanf("%d%d",&a,&b); solve(a,b); } return 0; }



生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
為碼而活
積分：4237
15粉絲
7關(guān)注
欄目熱點(diǎn)
關(guān)閉
程序員人生
主站蜘蛛池模板： 中国一级片在线观看 | 亚洲成人va | 国产伦精品一区二区三区免费迷 | 久久爱综合网 | 国产精品久久综合 | 正在播放国产一区二区 | 91精品国产色综合久久不卡粉嫩 | 日韩午夜影院 | 欧美一级夜夜爽 | 成人97精品毛片免费看 | 久久精品免费看 | 日本久久精品 | 色婷婷综合久久久久中文一区二区 | 欧美日韩一区二区三区四区 | 综合久久久久久久 | 日本精品在线视频 | 精品国产乱码久久久久久久软件 | 精品美女久久久久 | 日韩精品视频在线播放 | 国产精品123| av免费网站在线观看 | 欧美在线综合视频 | 国产一区二区三区视频 | 欧美日本在线播放 | 国产在线一区二区三区视频 | 91视频官网| 伊人网址 | 国产成人8x视频一区二区 | 日韩一区二区三区精品视频 | 91精品久久久久久久久久 | 91嫩草精品 | 91成人入口 | 99久久免费看视频 | 国产91精品久久久久久久网曝门 | 91成人观看 | 欧美性猛交xxxx免费看 | 日韩久久免费视频 | 91免费在线| 欧美一级黄色大片 | 99久久精品国产免费看不卡 | 日韩成人一区二区 |