제목 링크 제목: 0~N-1의 나무에서 N개의 점을 구하고 나무의 직경에 존재할 수 있는 점을 구하며 좌표를 오름차순으로 출력한다.
먼저 나무형 dp의 방식을 이용하여 나무의 직경을 구한 다음에 뿌리 dp를 바꾸는 방법에 따라 우리는 각 점을 중심으로 할 때 가장 먼 거리가 얼마나 되는지 구하여 나무의 직경을 구성할 수 있는지 판단할 수 있다.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, head[maxN], cnt;
struct Eddge
{
int nex, to;
Eddge(int a=-1, int b=0):nex(a), to(b) {}
} edge[maxN << 1];
inline void addEddge(int u, int v)
{
edge[cnt] = Eddge(head[u], v);
head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
int dp[maxN][2], maxD;
void dfs(int u, int fa)
{
for(int i=head[u], v; ~i; i=edge[i].nex)
{
v = edge[i].to;
if(v == fa) continue;
dfs(v, u);
if(dp[u][0] < dp[v][0] + 1)
{
dp[u][1] = dp[u][0];
dp[u][0] = dp[v][0] + 1;
}
else if(dp[u][1] < dp[v][0] + 1)
{
dp[u][1] = dp[v][0] + 1;
}
maxD = max(maxD, dp[u][0] + dp[u][1] + 1);
}
}
vector ans;
void change_root(int u, int fa, int deep)
{
if(max(deep, dp[u][1]) + dp[u][0] + 1 == maxD) ans.push_back(u);
for(int i=head[u], v; ~i; i=edge[i].nex)
{
v = edge[i].to;
if(v == fa) continue;
change_root(v, u, (dp[v][0] + 1 == dp[u][0] ? max(dp[u][1], deep) + 1 : max(dp[u][0], deep) + 1) );
}
}
inline void init()
{
cnt = 0; maxD = 0;
for(int i=0; i<=N; i++) head[i] = -1;
}
int main()
{
scanf("%d", &N);
init();
for(int i=1, u, v; i
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
01 가방 문제(DP 동적 계획)
n개의 무게와 가치가 각각 와이,vi인 물품이 있습니다.이 물품들 중에서 총 중량이 W를 초과하지 않는 물품을 골라 모든 선택 방안 중 가치 총화의 최대치를 구한다.
1<=n<=100
1<=wi,vi<=100
1<=...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
