P4281 [AHOI2008] Emergency Assembly/ Party

Title description

There is a very fun game on Happy Island called “Emergency Collection”. There are N waiting points scattered on the island, there are N-1 roads connecting them, and each road connects to two waiting points, and through these roads, all waiting points can be traveled from one point to another. One point costs one game currency.

The people participating in the game are in groups of three. At the beginning, all personnel are randomly scattered on each waiting point (each The point allows multiple people to wait at the same time), and each person has enough game currency (used to pay for the cost of using the road), map (marking the road connection between the waiting points), and dialogue machine (used to be with the same group Member contact). When the assembly number is sounded, the members of each group quickly contact each other. After knowing the waiting point where all the members of their group are located, they quickly determine an assembly point among the N waiting points, and all members in the group will gather at the assembly point. The group with the least cost for the assembly will be the winner of the game.

Xiao Keke and his friends invite you to join this game. You choose the meeting point. Smart you can complete this Quest, help Cocoa win the game?

input format< /h3>

Two positive integers on the first line N and M (N<=500000, M<=500000), separated by a space. Respectively indicate the number of waiting points (the waiting points are also numbered from 1 to N) and the number of times needed to complete the collection to win the prize. Then there are N-1 lines, each line is separated by two positive integers A and B, separated by a space, indicating that there is a way between the waiting point numbered A and numbered B. Then there are M lines. Each line uses three positive integers to represent the number of Cocoa, Cocoa's friends and your waiting point before a certain collection.

output format< /h3>

There are M lines in total, each line Two numbers P and C are separated by a space. The i-th row indicates that the i-th assembly point is selected at the waiting point numbered P, and the total cost of assembly is C game coins.

input and output sample

Enter #1

6 4
1 2
twenty three  
twenty four 
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Output#1

Instructions/Tips

Tips:

In 40% of the data, N<=2000, M<=2000
In 100% of the data, N<=500000, M<=500000

sol: The answer is obviously lca. Use the st table to find lca. Two of the three lca should be the same, that is, to go to another lca is the best. The sum of the distances is the depth of the three nodes-three The depth of each lca

#include 

using namespace std;

typedef int ll;

inline ll read()

{

 ll s=0; bool f=0; char ch=' ';

 while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}

 while(isdigit(ch)) {s=(s<< 3)+(s<<1)+(ch^48 ); ch=getchar();}

 return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

 if(x<0) {putchar(< span style="color: #800000;">'-' ); x=-x;}

 if(x<10) {putchar(x+ '0'); return;}

 write(x/10); putchar((x%10< /span>)+'0');

}

#define W(x) write(x),putchar(‘ ‘)

#define Wl(x) write(x),putchar(‘
’)

const int N=1000005,M=2000005;

int n,m,nn;

int tot=0,Next[M],to[M],head[N];

int clk=0,id[N],eul[M],dep[M];

int st[M][23];

inline void Link(int x,int y){Next[++tot]=head[x]; to[tot]=y; head[x]=tot;}

inline void dfs(int x,int fat,int dd)

{

 int i;

 id[x]=++clk;

 eul[clk]=x;

 dep[clk]=dd;

 for(i=head[x];i;i=Next[i]) if(to[i]!=fat)

 {

 dfs(to[i],x,dd+1);

 eul[++clk]=x;

 dep[clk]=dd;

}

}

inline void pre(int n)

{

 int i,j;

 for(i=1;i<=n ;i++) st[i][0]=i;

 for(i=1;i<=< span style="color: #800080;">19;i++)

 {

 for(j=1;j<=n ;j++)

 {

 int a=st[j][i-1],b=st[j+(1<<(i-1)) ][i-1];

 if(dep[a]else st[j][i]=b;

}

}

}

inline int ask(int x,int y)

{

 x=id[x]; y=id[y]; if(x>y) swap(x,y);

 int oo=log2(y-x+1< span style="color: #000000;">);

 int a=st[x][oo],b=st[y-(1<1][oo];

 if(dep[a]return< /span> eul[a]; else return eul[b];

}

int main()

{

 int i,x,y,z;

 R(n); R(m);

 for(i=1;i)

 {

 R(x); R(y); Link(x,y); Link(y,x);

}

 dfs(1,0,0);

 pre(clk);

 while(m--)

 {

 R(x); R(y); R(z);

 int l1=ask(x,y),l2=ask(x,z),l3=ask(y,z),ll;

 if(l1==l2) ll=l3;else if(l1==l3) ll=l2;else ll=l1;

 W(ll); Wl(dep[id[x]]+dep[id[y]]+dep[id[z]]-dep[id[l1]]-dep[id [l2]]-dep[id[l3]]);

}

 return 0;

}

/*

input

6 4

1 2

2 3

2 4

4 5

5 6

4 5 6

6 3 1

2 4 4

6 6 6

output

5 2

2 5

4 1

6 0

*/

View Code

Xiao Keke and his friends invite you to join this game. You choose the meeting point. Smart you can complete this Quest, help Cocoa win the game?

The first line of two positive integers N and M (N<=500000, M<= 500000), separated by a space. Respectively indicate the number of waiting points (the waiting points are also numbered from 1 to N) and the number of times needed to complete the collection to win the prize. Then there are N-1 lines, each line is separated by two positive integers A and B, separated by a space, indicating that there is a way between the waiting point numbered A and numbered B. Then there are M lines. Each line uses three positive integers to represent the number of Cocoa, Cocoa's friends and your waiting point before a certain collection.

There are a total of M lines, each line has two numbers P and C, separated by a space . The i-th row indicates that the i-th assembly point is selected at the waiting point numbered P, and the total cost of assembly is C game coins.

Enter #1

6 4
1 2
twenty three  
twenty four 
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Output#1

Enter #1

6 4
1 2
twenty three  
twenty four 
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

Output #1

Tips:

In 40% of the data, N<=2000, M<=2000
In 100% of the data, N<= 500000, M<=500000

sol: The answer should obviously be lca, use the st table to find lca, two of the three lca should be the same, it is the best to go to another lca, the sum of the distance is the depth of the three nodes-the depth of the three lca

#include 

using namespace std;

typedef int ll;

inline ll read()

{

 ll s=0; bool f=0; char ch=' ';

 while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}

 while(isdigit(ch)) {s=(s<< 3)+(s<<1)+(ch^48 ); ch=getchar();}

 return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

 if(x<0) {putchar(< span style="color: #800000;">'-' ); x=-x;}

 if(x<10) {putchar(x+ '0'); return;}

 write(x/10); putchar((x%10< /span>)+'0');

}

#define W(x) write(x),putchar(‘ ‘)

#define Wl(x) write(x),putchar(‘
’)

const int N=1000005,M=2000005;

int n,m,nn;

int tot=0,Next[M],to[M],head[N];

int clk=0,id[N],eul[M],dep[M];

int st[M][23];

inline void Link(int x,int y){Next[++tot]=head[x]; to[tot]=y; head[x]=tot;}

inline void dfs(int x,int fat,int dd)

{

 int i;

 id[x]=++clk;

 eul[clk]=x;

 dep[clk]=dd;

 for(i=head[x];i;i=Next[i]) if(to[i]!=fat)

 {

 dfs(to[i],x,dd+1);

 eul[++clk]=x;

 dep[clk]=dd;

}

}

inline void pre(int n)

{

 int i,j;

 for(i=1;i<=n ;i++) st[i][0]=i;

 for(i=1;i<=< span style="color: #800080;">19;i++)

 {

 for(j=1;j<=n ;j++)

 {

 int a=st[j][i-1],b=st[j+(1<<(i-1)) ][i-1];

 if(dep[a]else st[j][i]=b;

}

}

}

inline int ask(int x,int y)

{

 x=id[x]; y=id[y]; if(x>y) swap(x,y);

 int oo=log2(y-x+1< span style="color: #000000;">);

 int a=st[x][oo],b=st[y-(1<1][oo];

 if(dep[a]return< /span> eul[a]; else return eul[b];

}

int main()

{

 int i,x,y,z;

 R(n); R(m);

 for(i=1;i)

 {

 R(x); R(y); Link(x,y); Link(y,x);

}

 dfs(1,0,0);

 pre(clk);

 while(m--)

 {

 R(x); R(y); R(z);

 int l1=ask(x,y),l2=ask(x,z),l3=ask(y,z),ll;

 if(l1==l2) ll=l3;else if(l1==l3) ll=l2;else ll=l1;

 W(ll); Wl(dep[id[x]]+dep[id[y]]+dep[id[z]]-dep[id[l1]]-dep[id [l2]]-dep[id[l3]]);

}

 return 0;

}

/*

input

6 4

1 2

2 3

2 4

4 5

5 6

4 5 6

6 3 1

2 4 4

6 6 6

output

5 2

2 5

4 1

6 0

*/

View Code

share picture

#include 

using namespace std;

typedef int ll;

inline ll read()

{

 ll s=0; bool f=0; char ch=' ';

 while(!isdigit(ch)) {f|=(ch=='-'); ch=getchar();}

 while(isdigit(ch)) {s=(s<< 3)+(s<<1)+(ch^48 ); ch=getchar();}

 return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

 if(x<0) {putchar(< span style="color: #800000;">'-' ); x=-x;}

 if(x<10) {putchar(x+ '0'); return;}

 write(x/10); putchar((x%10< /span>)+'0');

}

#define W(x) write(x),putchar(‘ ‘)

#define Wl(x) write(x),putchar(‘
’)

const int N=1000005,M=2000005;

int n,m,nn;

int tot=0,Next[M],to[M],head[N];

int clk=0,id[N],eul[M],dep[M];

int st[M][23];

inline void Link(int x,int y){Next[++tot]=head[x]; to[tot]=y; head[x]=tot;}

inline void dfs(int x,int fat,int dd)

{

 int i;

 id[x]=++clk;

 eul[clk]=x;

 dep[clk]=dd;

 for(i=head[x];i;i=Next[i]) if(to[i]!=fat)

 {

 dfs(to[i],x,dd+1);

 eul[++clk]=x;

 dep[clk]=dd;

}

}

inline void pre(int n)

{

 int i,j;

 for(i=1;i<=n ;i++) st[i][0]=i;

 for(i=1;i<=< span style="color: #800080;">19;i++)

 {

 for(j=1;j<=n ;j++)

 {

 int a=st[j][i-1],b=st[j+(1<<(i-1)) ][i-1];

 if(dep[a]else st[j][i]=b;

}

}

}

inline int ask(int x,int y)

{

 x=id[x]; y=id[y]; if(x>y) swap(x,y);

 int oo=log2(y-x+1< span style="color: #000000;">);

 int a=st[x][oo],b=st[y-(1<1][oo];

 if(dep[a]return< /span> eul[a]; else return eul[b];

}

int main()

{

    int i,x,y,z;

    R(n); R(m);

    for(i=1;i)

 {

        R(x); R(y); Link(x,y); Link(y,x);

}

    dfs(1,0,0);

    pre(clk);

    while(m--)

 {

        R(x); R(y); R(z);

        int l1=ask(x,y),l2=ask(x,z),l3=ask(y,z),ll;

        if(l1==l2) ll=l3;else if(l1==l3) ll=l2;else ll=l1;

        W(ll); Wl(dep[id[x]]+dep[id[y]]+dep[id[z]]-dep[id[l1]]-dep[id[l2]]-dep[id[l3]]);

}

 return 0;

}

/*

input

6 4  

1 2  

2 3  

2 4 

4 5

5 6

4 5 6

6 3 1

2 4 4 

6 6 6

output

5 2

2 5

4 1

6 0

*/

View Code

#include 

using namespace std;

typedef int ll;

inline ll read()

{

    ll s=0; bool f=0; char ch=‘ ‘;

    while(!isdigit(ch)) {f|=(ch==‘-‘); ch=getchar();}

    while(isdigit(ch)) {s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}

    return (f)?(-s):(s);

}

#define R(x) x=read()

inline void write(ll x)

{

    if(x<0) {putchar(‘-‘); x=-x;}

    if(x<10) {putchar(x+‘0‘); return;}

    write(x/10); putchar((x%10)+‘0‘);

}

#define W(x) write(x),putchar(‘ ‘)

#define Wl(x) write(x),putchar(‘
‘)

const int N=1000005,M=2000005;

int n,m,nn;

int tot=0,Next[M],to[M],head[N];

int clk=0,id[N],eul[M],dep[M];

int st[M][23];

inline void Link(int x,int y){Next[++tot]=head[x]; to[tot]=y; head[x]=tot;}

inline void dfs(int x,int fat,int dd)

{

    int i;

    id[x]=++clk;

    eul[clk]=x;

    dep[clk]=dd;

    for(i=head[x];i;i=Next[i]) if(to[i]!=fat)

 {

        dfs(to[i],x,dd+1);

        eul[++clk]=x;

        dep[clk]=dd;

}

}

inline void pre(int n)

{

    int i,j;

    for(i=1;i<=n;i++) st[i][0]=i;

    for(i=1;i<=19;i++)

 {

        for(j=1;j<=n;j++)

 {

            int a=st[j][i-1],b=st[j+(1<<(i-1))][i-1];

            if(dep[a]else st[j][i]=b;

}

}

}

inline int ask(int x,int y)

{

    x=id[x]; y=id[y]; if(x>y) swap(x,y);

    int oo=log2(y-x+1);

    int a=st[x][oo],b=st[y-(1<1][oo];

    if(dep[a]return eul[a]; else return eul[b];

}

int main()

{

    int i,x,y,z;

    R(n); R(m);

    for(i=1;i)

 {

        R(x); R(y); Link(x,y); Link(y,x);

}

    dfs(1,0,0);

    pre(clk);

    while(m--)

 {

        R(x); R(y); R(z);

        int l1=ask(x,y),l2=ask(x,z),l3=ask(y,z),ll;

        if(l1==l2) ll=l3;else if(l1==l3) ll=l2;else ll=l1;

        W(ll); Wl(dep[id[x]]+dep[id[y]]+dep[id[z]]-dep[id[l1]]-dep[id[l2]]-dep[id[l3]]);

}

 return 0;

}

/*

input

6 4  

1 2  

2 3  

2 4 

4 5

5 6

4 5 6

6 3 1

2 4 4 

6 6 6

output

5 2

2 5

4 1

6 0

*/

Drums 4281, gongs

luogu4281

P4281 [AHOI2008] Emergency Assembly/ Party

Title description

output format< /h3>

There are M lines in total, each line Two numbers P and C are separated by a space. The i-th row indicates that the i-th assembly point is selected at the waiting point numbered P, and the total cost of assembly is C game coins.

input and output sample

Instructions/Tips

Leave a Comment Cancel reply

P4281 [AHOI2008] Emergency Assembly/ Party

Title description

output format< /h3> There are M lines in total, each line Two numbers P and C are separated by a space. The i-th row indicates that the i-th assembly point is selected at the waiting point numbered P, and the total cost of assembly is C game coins.

input and output sample

Instructions/Tips

Leave a Comment Cancel reply

output format< /h3>

There are M lines in total, each line Two numbers P and C are separated by a space. The i-th row indicates that the i-th assembly point is selected at the waiting point numbered P, and the total cost of assembly is C game coins.