生活随笔
收集整理的這篇文章主要介紹了
牛客网【每日一题】7月8日 Alliances
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
來源：牛客網
文章目錄
時間限制：C
/C
++ 5秒，其他語言
10秒
空間限制：C
/C
++ 262144K，其他語言
524288K
64bit IO Format
: %lld
題目描述
樹國是一個有n個城市的國家，城市編號為1～n。連接這些城市的道路網絡形如一棵樹，
即任意兩個城市之間有恰好一條路徑。城市中有k個幫派，編號為1～k。每個幫派會占據一些城市，以進行非法交易。有時幫派之間會結盟，這就使得城市更加不安全了。同一座城市中可能有多個幫派。
當一些幫派結成聯盟時，他們會更加強大，同時也更加危險。他們所控制的城市數會顯著增加。具體地，一個聯盟控制的城市是聯盟中所有幫派所占據的城市，再加上這些城市兩兩之間路徑上的所有城市。
shy是樹國的市長，他想要選擇一個城市作為首都。在決定之前，他要先做一些調研。為此，他找來你幫他回答一些詢問，你能做到嗎？在每個詢問中，shy會選擇一個城市作為首都，同時會告訴你當前活躍的幫派的集合。在這個詢問中，你只需要考慮給定的集合中的幫派，其他的幫派你可以當作不存在。已知給定集合中的這些幫派結成了聯盟，shy希望抓獲聯盟中的人，以得到關于整個聯盟的一些信息。為此，他要找到被聯盟控制的所有城市中離首都最近的一座城市到首都的距離。有可能首都本身就被控制了，此時答案為0。請注意，詢問之間相互獨立，互不影響。
輸入描述:
輸入的第一行包含一個整數n，代表樹國中的城市數。 接下來n?1行，每行包含兩個整數u和v，代表城市u和v之間存在一條道路。
接下來一行包含一個整數k，代表樹國中的幫派數。
接下來k行，每行描述一個幫派。第i行的第一個整數c[i]代表第i個幫派占據的城市數，接下來c[i]個整數，代表被第i個幫派占據的城市。
接下來一行包含一個整數Q，代表詢問數。
接下來Q行，每行描述一個詢問。每行的前兩個整數V和t[i]代表本次詢問中的首都與需要考慮的幫派集合的大小。接下來t[i]個整數代表本次詢問中需要考慮的幫派。.
輸出描述:
對于每個詢問，輸出一行，包含一個整數，代表詢問的答案。
示例1
輸入
7
1 2
1 3
2 4
2 5
3 6
3 7
2
2 6 7
1 4
3
5 1 2
1 1 1
5 2 1 2
輸出
2
1
1
備注:
對于30%的數據，1≤n,k,Q≤1000, 1≤每個幫派占據城市數之和≤1000, 1≤每個詢問中考慮的幫派數之和≤1000
對于60%的數據，1≤n,k,Q≤100000, 1≤每個幫派占據城市數之和≤100000, 1≤每個詢問中考慮的幫派數之和≤100000
對于100%的數據，1≤n,k,Q≤500000, 1≤每個幫派占據城市數之和≤500000, 1≤每個詢問中考慮的幫派數之和≤500000
題解：
第一反應lca，最近好多lca的題
題目本質就是求一個點（即題目中的首都）到lca（x,y）上的點（即被控制的城市）的最短路徑
被控制的城市其實就形成了一個子樹
分情況討論：
1.城市不在被控制的子樹里面（如圖）
紫色是城市，橙色是被控制子樹，那距離就是首都到子樹的距離
sum=dep[首都]+dep[lca(城市x)]-dep[lca(城市x，首都)]
城市x就是lca（x,y）的值(x和y就是題目所給的幫派)
2.首都被控制
首都被控制分為直接控制（幫派點為首都）
或間接控制（首都在幫派之間的線路上）
那距離就是0
3.首都沒被控制，但是首都在被控制的子樹中
（首都的前驅被控制，后繼沒被控制）
對于這種情況我們就要找首都的的前驅后繼點，這樣好判斷距離
可以用dfs序，因為dfs序就保存著各個點的順序
然后可以用二分來降低復雜度
如果首都到LCA的路徑上存在一個點x（x被占領），x！=lca，那么答案就是首都到最近一個符合這個條件的點
lca詳細講解
dfs序詳細講解
為什么這些知識點我都會，但是我就不會做題。。哭o(╥﹏╥)o
代碼：
寫完再加上。。。（最近有點懶）
好吧我放棄了，寫完一直改，一直wa，難受自閉了
借鑒的大佬的代碼
#include<bits/stdc++.h>
using namespace std
;
typedef long long LL
;
const int MAX_N
=1e6+20;
const int DEG
=20;
const int INF
=0x3f3f3f3f;
const LL MOD
=1e9+7;
int T
;
int N
;
int head
[MAX_N
],tot
;
struct Edge
{int to
,nxt
;
}edge
[MAX_N
*2];
void addedge(int u
,int v
){edge
[tot
].to
=v
;edge
[tot
].nxt
=head
[u
];head
[u
]=tot
++;
}
void init(){tot
=0;memset(head
,-1,sizeof(head
));
}
int fa
[MAX_N
][DEG
];
int deg
[MAX_N
];
void BFS(int root
){queue
<int>que
;deg
[root
]=0;fa
[root
][0]=root
;que
.push(root
);while(!que
.empty()){int tmp
=que
.front();que
.pop();for(int i
=1;i
<DEG
;i
++){fa
[tmp
][i
]=fa
[fa
[tmp
][i
-1]][i
-1];}for(int i
=head
[tmp
];i
!=-1;i
=edge
[i
].nxt
){int v
=edge
[i
].to
;if(v
==fa
[tmp
][0])continue;deg
[v
]=deg
[tmp
]+1;fa
[v
][0]=tmp
;que
.push(v
);}}
}
int LCA(int u
,int v
){if(deg
[u
]>deg
[v
])swap(u
,v
);int hu
=deg
[u
],hv
=deg
[v
];int tu
=u
,tv
=v
;for(int det
=hv
-hu
,i
=0;det
;det
>>=1,i
++){if(det
&1)tv
=fa
[tv
][i
];}if(tu
==tv
)return tu
;for(int i
=DEG
-1;i
>=0;i
--){if(fa
[tu
][i
]==fa
[tv
][i
])continue;tu
=fa
[tu
][i
];tv
=fa
[tv
][i
];}return fa
[tu
][0];}
int dfsn
[MAX_N
];
int pos
[MAX_N
];
int dfst
=0;
void DFS(int v
,int fa
){dfsn
[v
]=++dfst
;pos
[dfst
]=v
;for(int i
=head
[v
];i
!=-1;i
=edge
[i
].nxt
){int u
=edge
[i
].to
;if(u
==fa
)continue;DFS(u
,v
);}
}
int dis(int u
,int v
){int res
=deg
[u
]+deg
[v
]-2*deg
[LCA(u
,v
)];return res
;
}
int lc
[MAX_N
];
vector
<int> g
[MAX_N
];
int n
;
int u
,v
;
void input(){}
int t
[MAX_N
];
int main(){init();scanf("%d",&n
);for(int i
=1;i
<n
;i
++){scanf("%d%d",&u
,&v
);addedge(u
,v
);addedge(v
,u
);}BFS(1);DFS(1,-1);int k
;scanf("%d",&k
);for(int i
=1;i
<=k
;i
++){int c
,x
;scanf("%d",&c
);for(int j
=1;j
<=c
;j
++){scanf("%d",&x
);if(j
==1)lc
[i
]=x
;else lc
[i
]=LCA(lc
[i
],x
);g
[i
].push_back(dfsn
[x
]);}sort(g
[i
].begin(),g
[i
].end());}int q
,u
,cnt
;scanf("%d",&q
);while(q
--){scanf("%d%d",&u
,&cnt
);for(int i
=1;i
<=cnt
;i
++){scanf("%d",&t
[i
]);}int lca
=lc
[t
[1]];for(int i
=2;i
<=cnt
;i
++)lca
=LCA(lca
,lc
[t
[i
]]);if(LCA(lca
,u
)!=lca
){printf("%d\n",dis(lca
,u
));continue;}int ans
=INF
;for(int i
=1;i
<=cnt
;i
++){int tmp
=t
[i
];auto p
=lower_bound(g
[tmp
].begin(),g
[tmp
].end(),dfsn
[u
]);if(p
!=g
[tmp
].end()){ans
=min(ans
,dis(u
,LCA(u
,pos
[*p
])));}if(p
!=g
[tmp
].begin()){ans
=min(ans
,dis(u
,LCA(u
,pos
[*prev(p
)])));}}printf("%d\n",ans
);}}
總結
以上是生活随笔為你收集整理的牛客网【每日一题】7月8日 Alliances的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
