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

  1. 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 .* ...

  2. 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 ...

  3. 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 -------------------------------------------------------------------- ...

  4. 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\)... ...

  5. hdu 5052 The tree chain splits

    Yaoge’s maximum profit Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/ ...

  6. 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 ...

  7. 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 , ...

  8. 【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 ...

  9. 【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

  1. 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 ...

  2. 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 ...

  3. 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 ...

  4. 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 ...

  5. [ Reprint ]Access to the path &#39;&#39; 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 ...

  6. Province 、 City 、 Three level linkage of districts and counties Html Code

    <!DOCTYPE html><html><head> <meta http-equiv="Content-Type" content=& ...

  7. js Realize text box input text number limit code

    html: <div class="curr_eval_box">                <input type="hidden" n ...

  8. 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 ...

  9. One spinner Control

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

  10. 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 ...