Positive solution : structure

Problem solving report :

Portal

Another interactive question ! I love you !

This is really , Wonderful ! Very immortal ! It's very, very thinking !

Let's talk about it directly

It's really simple

That is to ask the number of a point in the other party's connection block , Write it down as x

If x The positive common point in my block is x,continue, Don't talk about luck x

And then ask me about my connection block x The nearest point is the number of the other side , Write it down as y

If y It belongs to the other party , Ook , There's something in common , Namely y

If it doesn't belong to , Let's make sesame oil public ,GG

Explain that

If it belongs to this, needless to say, obviously

And then if it doesn't belong to , We make x For the root of a tree , Then I must be all in the x On every tree in the world ( Because sesame oil goes through x Well

Then leave x The nearest node is the root of the subtree

If the root is not in the other party's connection block, other nodes will have more opportunities

So let's make sesame oil public !over!

( do not know why ,,, I use it psj But his code runs fast and I run slow ,,, It's very sad TT

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define il inline
#define rg register
#define rp(i,x,y) for(register ll i=x;i<=y;++i) const ll N=+;
struct ed{ll from,to,nxt;void clr(){from=;to=;nxt=;}}edge[N<<];
ll head[N],cnt;
bool my[N],your[N]; il void ad(int x,int y){edge[++cnt].to=y;edge[cnt].nxt=head[x];head[x]=cnt;}
il ll dfs(int num,int fa)
{
if(my[num])return num;
for(rg ll i=head[num];i;i=edge[i].nxt)
{
if(edge[i].to==fa)continue;
ll temp=dfs(edge[i].to,num);
if(temp!=-)return temp;
}
return -;
}
int main()
{
ll T;cin>>T;
while(T--)
{
ll n,tmp,gdgs,root;cin>>n;
memset(head,,sizeof(head));rp(i,,(n<<))edge[i].clr();memset(my,,sizeof(my));memset(your,,sizeof(your));cnt=;
rp(i,,n-){ll x,y;cin>>x>>y;ad(x,y);ad(y,x);}
cin>>tmp;rp(i,,tmp)cin>>gdgs,my[gdgs]=;cin>>tmp;rp(i,,tmp)cin>>gdgs,your[gdgs]=;
cout<<"B "<<gdgs<<endl;cout.flush();cin>>root;
if(my[root]){cout<<"C "<<root<<endl;cout.flush();continue;}
ll ques=dfs(root,);
if(ques==-){cout<<"C -1\n";cout.flush();continue;}
cout<<"A "<<ques<<endl;cout.flush();
ll as;cin>>as;
if(your[as]){cout<<"C "<<ques<<endl;cout.flush();continue;}
cout<<"C -1\n";cout.flush();
}
return ;
}

I made the first interactive question in my life !

CF1044B Intersecting Subtrees structure + More about tree theory

  1. C# combination Jquery LigerUI Tree Plug in tree

    Jquery LigerUI Tree yes Jquery LigerUI() One of the plug-ins , Using it, you can quickly build a tree menu . ha-ha No more bullshit , Go straight to the point , Let's introduce C# combination ligerui Two ways to construct a tree menu 1 ...

  2. java according to The root node and all its child members Construct trees tree

    Entity class entity package com.ompa.biz.entity; import java.util.ArrayList; import java.util.List; public cla ...

  3. C# Recursive tree data structure ( Generic ), How to construct ? How to query ?

    Ten years of Hedong , Ten years in Hexi , Don't deceive young people into being poor . knowledge has no limit , Keep improving It's rare to have a free morning , Just write a blog . First , We need to prepare a table , Here is an example : create table TreeTable ( TreeId ) no ...

  4. The design and implementation of simple common permission system ( Four ): Do not maintain level, Construct trees recursively

    In chapter three , By maintaining the depth of the node level, By iterating over all the nodes , Just once , It's a tree .  This article , Another way . The advantage is : Do not maintain the depth of the node level, When adding and modifying nodes , No maintenance . Recursive implementation , The code is clear ...

  5. The design and implementation of simple common permission system ( 5、 ... and ): Do not maintain the depth of the node level, Manual calculation level, Construct trees

      This way, , It's similar to the third one . The difference is , The depth of the node is not stored in the database level, When adding and modifying , No maintenance . It is , In the program , In real time . As for the back , according to level Ascending sort , Then iterate all the nodes to construct the tree , And ...

  6. Object-Widgets-Quick Construct trees

    Object Tree When it comes to QObject Create a... For the parent class QObject when ,  It will be added to the parent class's children In the list .  Deconstruction time , QObjet  I'll check myself first children,  In turn, it's deconstructed ,  however ...

  7. according to In the sequence traversal and After traversing the construction tree (Presentation)(C++)

    It's Friday again , The weekend is finally over . It's just a whim to write this essay , I asked a friend in the afternoon PAT How did you do on the test , By the way, take a look at his test , There's one last question in it , It's about giving middle order traversal and post order traversal, and then finding a hierarchical traversal . wait , I'm looking for ...

  8. CF1003E Tree Constructing structure + Tree theory

    Positive solution : structure Problem solving report : Portal ! This is sesame oil translation duck ,,, Let's get down to the topic first QAQ Build a tree n A little bit , The diameter is d, Each dot does not exceed k The tree of In fact, I jio It's still relatively simple ,,, First construct a diameter , It's one ...

  9. The structure on the tree The trees divide + The nature of the center of gravity of a tree Codeforces Round #190 (Div. 2) E

    http://codeforces.com/contest/322/problem/E E. Ciel the Commander time limit per test 1 second memor ...

Random recommendation

  1. Python Black hat programming 4.1 Sniffer( Sniffer ) Data capture for ( On )

    Python Black hat programming 4.1 Sniffer( Sniffer ) Data capture for ( On ) Network sniffer , It is a technology to monitor the data packets flowing through the local network card , Sniffer is the software that uses this technology to capture and analyze data . Write sniffers , Capturing data is a front-end function , ...

  2. Swift The sense of writing microblog

    First Swift It's apple. 2014 Nianli's programming language . We can see the development trend   Here we provide    

  3. Android GridView Use

    Android Of GridView Control is used to organize a series of space into a two-dimensional grid display, the application of more is the combination of picture display, I will talk about an example in detail below First write a class inheritance BaseAdapter 1. Java Code 1 ...

  4. jQuery Official basic course notes ( Reprint )

    This article is reproduced in Ruan Yifeng's blog , Content basis , The structure is clear , yes jquery Rare information for beginners , very nice , Praise one . Ruan Yifeng :jQuery Official basic course notes jQuery Is currently the most widely used javascript function library . According to statistics ...

  5. [ Game templates 3] Win32 paint brush A brush graphics

    >_<:introduce the functions of define\create\use pen and brush to draw all kinds of line and s ...

  6. angular+selecte2(angular ng-repeat Rendering )

    One . Page code <select id="sponsorId" select2 ng-model="sponsorSelectedObj" ng-change ...

  7. Android_Notification

    xml file : <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns ...

  8. Color matrix Filter ColorMatrix

    Color matrix principle The three elements of color 1. Hue . Hue is commonly said to be " Color ", The change of hue is the change of color , The adjustment of hue is accompanied by the change of red, orange, yellow, green, blue and purple . 2. brightness . Mingdu is popularly said to be " Illuminance &quo ...

  9. Use SqlCacheDependency Dependencies invalidate the cache when the database changes

    SqlCacheDependency You can make the cache invalid when the database or a table or field of the database changes . It's useful for some information that needs to be displayed in time . need .net2.0 Later sql server2005 And later versions ...

  10. Baidu statistics API Use

    Baidu statistics API Use When building your own blog , I hope I can have a log system , Be able to see PV.UV Etc , At the same time, I also built a ELK System , Unfortunately, the server configuration is too low (1GHZ+1G Memory ), It doesn't work at all . You can only use a third party's Day ...