Description
There are \(n\) railway stations. A chain hotel wants to open restaurants at the railway station, but the government does not allow it to operate at two connected railway stations at the same time. Any two railway stations have one and only one route. Now that the profit of opening a restaurant at each railway station is known, find the maximum profit of this chain hotel.
- Format
- Input
- The first line is a positive integer \(t (≤5)\), indicating the number of data groups; in each group of data, the first line is a positive integer \(n (≤10^5)\), which indicates the number of train stations, the number is from \(1\) to \(n\), and the next \(n-1\) lines , Each line has two positive integers \(a\), \(b\) \((a, b≤n)\), respectively, indicating that there is a direct path between \(a\) and \(b\) railway stations, and the last line is \(n\) positive integers \(w_i (≤10^4)\), respectively Profit from operating a restaurant at a railway station.
- Output
Output the maximum profit.
- Sample
- Input
- 2
- 6
- 1 3
- 3 4
- 4 5
- 2 3
- 4 6
- 10 20 25 40 30 30
- ???
- Output
- 90 ?
- Sample Code
- #include <cstdio>
- #include <cstring>
- const int N=100010;
- struct Edge{
- int v, next;
- }edge[2*N];// 边集数组
- struct Head{
- int first, w;
- }head[N];
- int pos, ans, n, f[N], g[N];
- bool vis[N];
- inline int mx(int a, int b){
- return a>b ? a : b;
- }
- void in(int &s){
- char c=getchar();
- while (c<'0' || c>'9') c=getchar();
- for (s=0; c>='0' && c<='9'; c=getchar())
- s=s*10+c-'0';
- }
- void ins(int x, int y){
- pos++; edge[pos].v=y;
- edge[pos].next=head[x].first; head[x].first=pos;
- }
- void dfs(int r){
- vis[r]=1;
- f[r]=head[r].w, g[r]=0;
- for (int k=head[r].first; k; k=edge[k].next){
- int v=edge[k].v;
- if (!vis[v]){
- dfs(v);
- f[r]+=g[v];
- g[r]+=mx(f[v], g[v]);
- }
- }
- ans=mx(ans, mx(f[r], g[r]));
- }
- int main(){
- freopen("profit.in", "r", stdin);
- freopen("profit.out", "w", stdout);
- int t;
- scanf("%d", &t);
- while (t--){
- scanf("%d", &n);
- memset(vis, 0, sizeof(vis));
- memset(head, 0, sizeof(head));
- pos=0; ans=-1;
- int x, y;
- for (int i=1; i<n; i++){
- in(x), in(y); //scanf("%d %d", &x, &y);
- ins(x, y); ins(y, x);
- }
- for (int i=1; i<=n; i++)
- scanf("%d", &head[i].w);
- dfs(1);
- printf("%d\n", ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3683692.html