C. Li Hua and Chess
题意：给出一个棋盘长宽n,m，有一颗棋子在棋盘上，向八个方向走一步的路程代价都为1，现在进行最多3次询问，问能否确认棋子的位置
Solution
第一次做交互题，想很好想，先询问(1,1)，得到x，再询问(1+x,1+x)，得到y，最后询问(1+x,1+x-y)，如果得到的是0，则输出这个点，反之输出(1+x-y,1+x)
不过有个坑，看到了但是我只看到了一半，1+x可能比n或m小，所以第二次询问时要分别跟n和m判断一下，与1+x横坐标和纵坐标都取小，询问的时候也是
好像关闭了输入流就不能用fflush(stdout)?
void solve()
{
int n,m;cin>>n>>m;
cout<<"? 1 1"<<"\n";
cout.flush();
int x;cin>>x;
int y;
cout<<"? "<<n<<" "<<m<<"\n";
cout.flush();
cin>>y;
int ansx=0,ansy=0;
if(x+y==n)
{
cout<<"?"<<" "<<x<<" "<<x<<"\n";
cout.flush();
int z;cin>>z;
cout<<"!"<<" "<<x<<" "<<x-z<<"\n";
cout.flush();
}
else if(x+y==m)
{
cout<<"?"<<" "<<x<<" "<<x<<"\n";
cout.flush();
int z;cin>>z;
cout<<"!"<<" "<<x-z<<" "<<x<<"\n";
cout.flush();
}
}
D. Li Hua and Tree
题意：给出一颗树，每个节点上都有一个权值a[i]，定义重儿子为非叶子节点的子结点中子树大小最大的子结点
进行q次操作：
1:1 x，输出以x的子树和x上所有点的权值和
2:2 x，让x的重儿子的父节点变为x的父节点，让x的重儿子变成x的父节点，将如果x是叶子，不继续操作
Solution
操作很简单，树形dp记录最初的状态后，维护一下每个节点的重儿子即可，这里用set+结构体重载运算符维护
struct node
{
int x,y;
bool operator < (const node& b) const{
if(x!=b.x)return x > b.x;
return y < b.y;
}
};
int a[N];
vector<int>e[N];
int dp[N];
int t[N];
set<node>st[N];
int p[N];
void dfs(int x,int pre)
{
dp[x]=a[x];
t[x]=1;
for(auto it:e[x])
{
if(it==pre)continue;
dfs(it,x);
p[it]=x;
dp[x]+=dp[it];
t[x]+=t[it];
node xx;
xx.x=t[it],xx.y=it;
st[x].insert(xx);
}
}
void solve()
{
int n,q;cin>>n>>q;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,0);
//for(int i=1;i<=n;i++)cout<<dp[i]<<"\n";
while(q--)
{
int op,x;cin>>op>>x;
if(op==1)cout<<dp[x]<<"\n";
else
{
if(st[x].size()==0)continue;
int ts=st[x].begin()->x;
int ti=st[x].begin()->y;
int xx=dp[x]-dp[ti];
int yy=t[x]-ts;
st[p[x]].erase({t[x],x});
st[p[x]].insert({t[x],ti});
st[ti].insert({yy,x});
st[x].erase(st[x].begin());
dp[ti]=dp[x];
dp[x]=xx;
t[ti]=t[x];
t[x]=yy;
p[ti]=p[x];
p[x]=ti;
}
}
}