SPOJ QTREE (트 리 체인 분할 은 변 권 기반)

변 에 있어 서 한 그루 의 나무 에 뿌리 노드 를 제외 하고 모든 결점 이 하나의 변 에 유일 하 게 대응 하면 변 을 점 으로 바 꾸 는 문제 가 매우 좋다.
트 리 체인 분할 + 선분 트 리
루트 노드 조회 시 취사선택 문제 주의

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#pragma comment(linker, "/STACK:1024000000,1024000000");

using namespace std;

#define INF 0x3f3f3f3f
#define maxn 20003

int n;
int x[maxn],y[maxn];
int fir[maxn],u[maxn],v[maxn],w[maxn],nex[maxn];
int e_max;

int mx[maxn],mxt[maxn],mix[4*maxn];

int tot;
int son[maxn],siz[maxn],pos[maxn],fa[maxn],top[maxn],deep[maxn];

void init_()
{
    tot=0;
    memset(fir,-1,sizeof fir);
    memset(son,-1,sizeof son);
    memset(siz,0,sizeof siz);
    e_max=0;
}

inline void add_edge(int s,int t,int c)
{
    int e=e_max++;
    u[e]=s;
    v[e]=t;
    w[e]=c;
    nex[e]=fir[s];
    fir[s]=e;
}

void dfs1(int k,int pre,int d)
{
    deep[k]=d;
    fa[k]=pre;
    siz[k]++;
    for(int i=fir[k]; ~i; i=nex[i])
    {
        int e=v[i];
        if(e!=pre)
        {
            mxt[e]=w[i];
            dfs1(e,k,d+1);
            siz[k]+=siz[e];
            if(son[k]==-1||siz[son[k]]>1;
    init(l,mid,k<<1);
    init(mid+1,r,k<<1|1);
    mix[k]=max(mix[k<<1],mix[k<<1|1]);
}

inline void update(int d,int s,int l,int r,int k)
{
    if(s==l&&r==s)
    {
        mix[k]=d;
        return ;
    }
    int mid=l+r>>1;
    if(s<=mid) update(d,s,l,mid,k<<1);
    else update(d,s,mid+1,r,k<<1|1);
    mix[k]=max(mix[k<<1],mix[k<<1|1]);
}

inline int query(int s,int t,int l,int r,int k)
{
    if(s==l&&r==t)
    {
        return mix[k];
    }
    int mid=l+r>>1;
    if(t<=mid) return query(s,t,l,mid,k<<1);
    else if(s>mid) return query(s,t,mid+1,r,k<<1|1);
    else return max(query(s,mid,l,mid,k<<1),query(mid+1,t,mid+1,r,k<<1|1));
}

void Query(int s,int t)
{
    int ans=0;
    int f1=top[s],f2=top[t];
    while(f1!=f2)
    {
        if(deep[f1]deep[t]) swap(s,t);
    ans=max(ans,query(pos[s]+1,pos[t],1,tot-1,1));
    printf("%d
",ans);
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init_();
        scanf("%d",&n);
        for(int i=1; i

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

CodeForces 343D (트 리 체인 분할 + 선분 트 리)

The vertices of the tree are numbered from 1 to n with the root at vertex 1. Fill vertex v with water. Input The first l...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

SPOJ QTREE (트 리 체인 분할 은 변 권 기반)

좋은 웹페이지 즐겨찾기