Link to the original text https://www.cnblogs.com/zhouzhendong/p/UOJ53.html

# The question

Given a tree with n Tree of nodes .

Every point has a weight .

For each of these $i$ Given three parameters $a_i,b_i,c_i$ , From $i$ Starting from one point, the next point you can reach x You need to meet one of three requirements ：

1. x stay $a_i$ To $b_i$ On the simple path of .

2. x stay $a_i$ To $c_i$ On the simple path of .

3. x stay $c_i$ To $b_i$ On the simple path of .

Starting from any point , The weight of the passing node and the front k What's the length of the small route . Note that you can go through the nodes repeatedly .

Space restriction 100MB, The time limit 3s

$n,k\leq 5\times 10^5$

Make sure the answer is less than $10^8$.

# Answer key

because $k,n$ Isomorphism , So the later complexity analysis doesn't distinguish $n$ and $k$ .

First of all, the nodes that can be reached by each point are divided into no more than two chains .

Partition with tree chain + Line segment tree + Preprocessing heavy chain prefixes min , To achieve $O(\log n)$ Find the minimum weight point on a chain .

If we come violent , So obviously ：

Initially, all the points are thrown directly into a pile , The key words are the sum of node weights , Take out the smallest elements in turn , Every time I take out one , Just add a solution to the heap that you can get from this point , So just take it out k The next time .

Obviously, the complexity of time and space has withered .

So we consider splitting the tree chain 、 Mark these lines on the tree , The keywords for these tags are “ From the current state , Then walk to the point with the smallest weight in the interval to get the path length ”, When it's taken out of the heap, it splits the markers , You get a time complexity $O(n\log^2 n)$ Spatial complexity $O(n\log n)$ How to do it , It's still not enough to pass the question .

Consider changing the form of the tag to $(a,b)$ , Two endpoints in a chain . So when you take out this chain , Just update the heap state in two parts ：

1. Split the chain from the minimum weight point of the chain , Into two shorter chains , Add to the heap .

2. Starting from the minimum weight point of this chain , Up to two chains , Add to the heap .

So we get a spatial complexity $O(n)$ , Time complexity $O(n\log n)$ How to do it .

And then because the blogger is so big , Still stuck in space .

So I forced vector The array is written as an array simulation list , Write the system heap as a handwriting heap ……

Finally, I suddenly found out that he promised that the answer was less than 1e8 , It's not that the edge weight is less than 1e8 I was stunned when I went to school .

So many constants stuck before , In fact, you only need to change the data type of the storage path length from longlong Change to int Just fine ……

# Code

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL read(){

LL x=0,f=0;

char ch=getchar();

while (!isdigit(ch))

f|=ch=='-',ch=getchar();

while (isdigit(ch))

x=(x<<1)+(x<<3)+(ch^48),ch=getchar();

return f?-x:x;

}

const int N=500005;

int n,k;

struct Info{

int a,b,c,d;

}v[N];

struct Gragh{

static const int M=N*2;

int cnt,y[M],nxt[M],fst[N];

void clear(){

cnt=1;

memset(fst,0,sizeof fst);

}

void add(int a,int b){

y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;

}

}g;

int w[N];

int fa[N],depth[N],size[N],son[N],top[N],I[N],O[N],aI[N],Min[N],Time=0;

void dfs1(int x,int pre,int d){

depth[x]=d,fa[x]=pre,son[x]=0,size[x]=1;

for (int i=g.fst[x];i;i=g.nxt[i]){

int y=g.y[i];

if (y!=pre){

dfs1(y,x,d+1);

size[x]+=size[y];

if (!son[x]||size[y]>size[son[x]])

son[x]=y;

}

}

}

void ckwMin(int &x,int y){

if (w[x]>w[y])

x=y;

}

void dfs2(int x,int Top){

top[x]=Top,aI[I[x]=++Time]=x;

if (son[x])

ckwMin(Min[son[x]],Min[x]),dfs2(son[x],Top);

for (int i=g.fst[x];i;i=g.nxt[i]){

int y=g.y[i];

if (y!=fa[x]&&y!=son[x])

dfs2(y,y);

}

O[x]=Time;

}

int LCA(int x,int y){

int fx=top[x],fy=top[y];

while (fx!=fy){

if (depth[fx]<depth[fy])

swap(fx,fy),swap(x,y);

x=fa[fx],fx=top[x];

}

return depth[x]<depth[y]?x:y;

}

int isanc(int x,int y){

return I[x]<=I[y]&&I[y]<=O[x];

}

int go_up(int x,int y){

if (isanc(aI[I[y]+1],x))

return aI[I[y]+1];

int fx=top[x];

while (depth[fx]>depth[y]){

x=fx;

if (depth[fa[x]]>depth[y])

x=fa[x],fx=top[x];

else

break;

}

return x;

}

namespace Seg{

int v[N<<2];

void build(int rt,int L,int R){

if (L==R)

return (void)(v[rt]=aI[L]);

int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;

build(ls,L,mid);

build(rs,mid+1,R);

ckwMin(v[rt]=v[ls],v[rs]);

}

int query(int rt,int L,int R,int xL,int xR){

if (xL<=L&&R<=xR)

return v[rt];

int mid=(L+R)>>1,ls=rt<<1,rs=ls|1;

if (xR<=mid)

return query(ls,L,mid,xL,xR);

if (xL>mid)

return query(rs,mid+1,R,xL,xR);

int res=query(ls,L,mid,xL,xR);

ckwMin(res,query(rs,mid+1,R,xL,xR));

return res;

}

int query(int x,int y){

int ans=x,fx=top[x],fy=top[y];

while (fx!=fy){

if (depth[fx]<depth[fy])

swap(fx,fy),swap(x,y);

ckwMin(ans,Min[x]);

x=fa[fx],fx=top[x];

}

if (depth[x]>depth[y])

swap(x,y);

ckwMin(ans,query(1,1,n,I[x],I[y]));

return ans;

}

}

const int Size=N*5;

struct Node{

int a,b,len;

Node(){}

Node(int _a,int _b,int pre){

a=_a,b=_b;

len=pre+w[Seg :: query(a,b)];

}

}s[Size];

int stt=0;

bool cmp(int a,int b){

return s[a].len>s[b].len;

}

struct priority_Queue{

int v[Size],s;

bool empty(){

return s==0;

}

void up(int x){

int y=x>>1;

while (y){

if (cmp(v[y],v[x]))

swap(v[x],v[y]),x=y,y=x>>1;

else

break;

}

}

void down(int x){

int y=x<<1;

while (y<=s){

if (y<s&&cmp(v[y],v[y+1]))

y|=1;

if (cmp(v[x],v[y]))

swap(v[x],v[y]),x=y,y=x<<1;

else

break;

}

}

void pop(){

swap(v[1],v[s--]);

down(1);

}

int top(){

return v[1];

}

void push(int x){

v[++s]=x;

up(s);

}

}Q;

void push(Node x){

s[++stt]=x,Q.push(stt);

}

void Split(Node x,int Mi){

int a=x.a,b=x.b,m=Mi;

if (!isanc(m,a))

swap(a,b);

if (m!=a){

int aa=go_up(a,m);

push(Node(a,aa,x.len-w[m]));

}

if (m!=b){

int bb;

if (isanc(m,b))

bb=go_up(b,m);

else

bb=fa[m];

push(Node(b,bb,x.len-w[m]));

}

}

void solve(){

while (!Q.empty())

Q.pop();

for (int i=1;i<=n;i++)

push(Node(i,i,0));

while (k--){

Node now=s[Q.top()];

Q.pop();

printf("%d\n",now.len);

int x=Seg :: query(now.a,now.b);

Split(now,x);

if (~v[x].a)

push(Node(v[x].a,v[x].b,now.len));

if (~v[x].c)

push(Node(v[x].c,v[x].d,now.len));

}

}

int main(){

n=read(),k=read();

for (int i=1;i<=n;i++)

w[i]=read(),Min[i]=i;

g.clear();

for (int i=2;i<=n;i++){

int a=read();

g.add(a,i);

g.add(i,a);

}

for (int i=1;i<=n;i++)

v[i].a=read(),v[i].b=read(),v[i].c=read();

dfs1(1,0,0);

dfs2(1,1);

for (int i=1;i<=n;i++){

int a=v[i].a,b=v[i].b,c=v[i].c;

v[i].a=v[i].b=v[i].c=v[i].d=-1;

if (depth[c]<depth[b])

swap(b,c);

if (depth[b]<depth[a])

swap(a,b);

if (depth[c]<depth[b])

swap(b,c);

if (a==b||b==c){

v[i].a=a,v[i].b=c;

continue;

}

int ab=LCA(a,b),ac=LCA(a,c),bc=LCA(b,c);

if (ab==ac&&ab==bc){

int g=ab;

if (depth[a]>depth[g]){

v[i].a=a,v[i].b=b;

v[i].c=c,v[i].d=go_up(c,g);

continue;

}

v[i].a=b,v[i].b=c;

continue;

}

if (ab==bc)

swap(a,b),swap(ac,bc);

else if (ac==bc)

swap(a,c),swap(ab,bc);

if (depth[c]<depth[b])

swap(b,c),swap(ab,ac);

if (isanc(b,c)){

v[i].a=a,v[i].b=c;

continue;

}

v[i].a=a,v[i].b=b;

int d=go_up(c,bc);

v[i].c=c,v[i].d=d;

}

Seg :: build(1,1,n);

solve();

return 0;

}

## UOJ#53. 【UR #4】 After Santa The tree chain splits k More articles about short circuit

- UOJ#435. 【 Training team work 2018】Simple Tree The tree chain splits , Block
Link to the original text www.cnblogs.com/zhouzhendong/p/UOJ435.html Preface It's true that I can't write block questions . For a variety of reasons , I made a lot of mistakes when I was writing code , The most fatal thing is that the array is too small .* ...

- BZOJ 4326 The tree chain splits + Two points + Difference + Memorize
last year NOIP I didn't know how to divide the tree chain when I was young ! Or was UOJ I have a set of data cards . The idea of difference is still wonderful ! #include <iostream> #include <cstring> #i ...

- BZOJ 2157: tourism ( The tree chain splits )
The tree chain splits .. The sample is too big to adjust ... By the way, put up the data generator -------------------------------------------------------------------- ...

- Qtree3 Answer key （ The tree chain splits （ false ）+ Line segment tree +set）
unduly polite words that a friend does not need to say : Recently, Luo Gu added a lot of good questions ... The entrance to the original question This question seems to be SPOJ The topic , Pretty good . Look, there's no problem solution or one ... The question : Obviously .. Answer key : It's very violent : The tree chain splits ( false )+ Line segment tree +\(set\)... ...

- hdu 5052 The tree chain splits
Yaoge’s maximum profit Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/ ...

- Qtree3 Answer key （ The tree chain splits + Line segment tree +set）
unduly polite words that a friend does not need to say : Recently, Luo Gu added a lot of good questions ... The entrance to the original question This question seems to be SPOJ The topic , Pretty good . Look, there's no problem solution or one ... The question It's easy to understand, isn't it .. Answer key It's very violent : The tree chain splits ( false )+ Line segment tree + std :: set ...

- P1001 A+B Problem ( The tree chain splits )
This question tests our ability to construct models . Consider building a tree , There is... In the tree 3 Nodes , node 1 And nodes 2 Even one weight is zero a The edge of , node 1 And nodes 3 Even one weight is zero b The edge of , Obviously the answer is nodes 2 To the node 3 Shortest path . But that's not enough . Consider the nature of addition , ...

- 【BZOJ4196】[NOI2015] Package manager （ The tree chain splits ）
Click here to see the topic General meaning : Yes \(n\) Software package , Their dependency forms a tree . Now? , Ask you to install or uninstall a package , How many packages will be affected . The tree chain splits The question should be The tree chain splits Algorithm comparison of introductory topics bar . For Ann ...

- 【BZOJ2243】[SDOI2011] dyeing （ The tree chain splits ）
Click here to see the topic General meaning : There is a tree \(n\) Rootless trees with nodes and \(m\) Operations , And each node has a color . There are two types of operations : One is to color all the points between the paths on the two-point tree \(c\), The other is to ask the number of color segments between paths on two-point trees . ...

## Random recommendation

- hold php Upload sae The problem is to use IO
Application migration guide One , Why transplant applications SAE prohibit IO Write operations , Code directory cannot be written to . This means that the normal program uploads images . Generation cache and other operations cannot be performed in SAE Upper normal operation , At this time, you need to modify the code to make your program run in SA ...

- How to deal with the problem caused by stepping on the line ---lsof,strace
Two tracking processes linux command lsof -p pidstrace -p pid Quickly track where problems occur in the process . Because the process itself works well , But the interior has been waiting for the third party to answer , Cause the process to feign death . Quote from :http://li ...

- Baidu UEditor Simple installation, debugging and calling , Other online tutorials are too official , Not for beginners
For starters , As long as the function can be realized , Other settings are completely default . Preview : 1. First Download it on the official website , I won't go into that . Download and unzip to the directory you want , I'll put it in the root directory where you need to use the editor , Insert the following HTML Code : &l ...

- Shortcut key Ctrl+c、Ctrl+d、Ctrl+u、Ctrl+a、Ctrl+e
tab: Command or path completion key Ctrl +c : Terminate the current task command or program Ctrl +d : Exit the current user environment Ctrl +Shift+c ssh client ssh The command copied in the Ctrl + a To the beginning Ctrl ...

- [ Reprint ]Access to the path '' is denied. Solution
Original address :Access to the path '' is denied. Solution author : Waiting for the red apricot on the wall ccess to the path ' route ' is denied. I found a lot of information on the Internet , Finally, it's solved ...

- Province 、 City 、 Three level linkage of districts and counties Html Code
<!DOCTYPE html><html><head> <meta http-equiv="Content-Type" content=& ...

- js Realize text box input text number limit code
html: <div class="curr_eval_box"> <input type="hidden" n ...

- java,while The use of recycling , Receive user input , Do different things ！
package cn.edu.nwpu.java; import java.util.Scanner; public class IsoscelesTriangle { public static v ...

- One spinner Control
Layout file <?xml version="1.0" encoding="utf-8"?><android.support.constraint. ...

- Book one ：lesson fifteen.
original text :Your passports,please. A:Are you Swedish? B:No,we are not. We are Danish. A:Are your friends Dani ...