bzoj3124(树形dp)

Posted on   |   In

题解:

我们考虑找出任意一条直径的两个端点$x$,$y$ 对直径上的节点打上标记 对于其他不在直径上的点$v$ 找到其离的最近的标记点$pos$ 我们考虑当前$dis[pos]-dis[x]$与$dis[y]-dis[pos]$的大小关系然后判断$v$是否为分叉直径上的节点 若是则对原标记节点打上标记 最后的答案则为 每条边的权值是否等于分叉直径的条数

代码实现

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
 
ll dis[MAXN];int n;
bool vis[MAXN];
queue<int>que;
int bfs(int x){
    inc(i,1,n)vis[i]=dis[i]=0;
    que.push(x);vis[x]=1;
    while(!que.empty()){
    int y=que.front();que.pop();
    link(y){
        if(!vis[j->t])dis[j->t]=dis[y]+j->v,vis[j->t]=1,que.push(j->t);
    }
    }
    int pos=x;
    inc(i,1,n){
    if(dis[i]>dis[pos])pos=i;
    }
    return pos;
}
 
int fa[MAXN],p[MAXN];
ll sum[MAXN];
 
void dfs(int x,int pre){
    fa[x]=pre;
    link(x){
    if(j->t==pre)continue;
    sum[j->t]=sum[x]+j->v;
    dfs(j->t,x);
    }
}
 
void work(int y){
    inc(i,1,n)vis[i]=0;
    while(y){
    vis[y]=1;y=fa[y];
    }
}
 
void _dfs(int x,int y){
    int k;
    if(vis[x])k=x;else k=y;
    p[x]=k;
    link(x){
    if(j->t==fa[x])continue;
    _dfs(j->t,k);
    }
}
 
int ans[MAXN];
 
void __dfs(int x){
    link(x){
    if(j->t==fa[x])continue;
    __dfs(j->t);
    ans[x]+=ans[j->t];
    }
}
 
int main(){
    n=read();
    int x,y,z;
    inc(i,2,n)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    x=bfs(1);y=bfs(x);
    dfs(x,0);work(y);_dfs(x,x);
    ll len=sum[y]-sum[x];
    printf("%lld\n",sum[y]-sum[x]);
    int cnt=0;
    inc(i,1,n){
    if(vis[i])continue;
    ll t1=sum[i]-sum[p[i]];
    if(sum[p[i]]-sum[x]>sum[y]-sum[p[i]]){
        if(sum[p[i]]-sum[x]+t1==len)ans[p[i]]++,cnt++;
    }
    else if(sum[p[i]]-sum[x]<sum[y]-sum[p[i]]){
        if(sum[y]-sum[p[i]]+t1==len)ans[y]++,ans[p[i]]--,cnt++;
    }
    else{
        if(t1==sum[p[i]]-sum[x])cnt++;
    }
    }
    __dfs(x);
    int ans1=0;
    inc(i,1,n){
    if(i==x||!vis[i])continue;
    if(ans[i]==cnt)ans1++;
    }
    printf("%d\n",ans1);
}

题目描述

小Q最近学习了一些图论知识。根据课本，有如下定义。树：无回路且连通的无向图，每条边都有正整数的权值来表示其长度。如果一棵树有$N$个节点，可以证明其有且仅有$N-1$条边。 路径：一棵树上，任意两个节点之间最多有一条简单路径。我们用$dis(a,b)$表示点$a$和点$b$的路径上各边长度之和。称$dis(a,b)$为$a$ ,$b$两个节点间的距离。
直径：一棵树上，最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道，对于给定的一棵树，其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

输入描述

第一行包含一个整数$N$，表示节点数。
接下来$N-1$行，每行三个整数$a$,$ b$,$ c$ ,表示点 $a$和点$b$之间有一条长度为$c$的无向边。

输出描述

共两行。第一行一个整数，表示直径的长度。第二行一个整数，表示被所有
直径经过的边的数量。