6.28总结
得分情况
估分：100+0+0
实际：92+0+0
rank7
T1
推了两个小时的式子才推出来
容斥原理真奇妙...
忘记处理k=0的情况少了8分。数据还算良心
正解
题目要求有多少对数有恰好k个数相同。
记ans[i]表示恰好有k个数相同的对数
s[i]表示至少有k个数相同的对数
显然，(ans[i]=s[i]-sum_{j=i+1}^6 ans[j]*C_j^i)
可以枚举选哪些数来求s[i]
T2
考试一看题目背景，眼前一亮：阿萨辛！
然而题目不会做...
正解
这是一颗无根树，考虑把它转成有根树。
若重心只有一个，根就是重心，若重心有两个，就新建节点作为根，把原有的两个重心向新节点连边。
关于树同构，有一个神奇的性质：如果有两棵树，强制以重心为根，那么这两棵树同构当且仅当形成的两棵有根树同构。
一棵树的重心只有 1 个或 2 个，如果有 2 个（记为 u 和 v ），那么一定有边 (u,v)，而此时可以断开边 (u,v)，新建一个节点，分别向 u和 v 建边，这样新建的节点就是重心。
By xyz32768 的博客
选了重心作为根的好处是： 同构的子树之间可以互相调换。
用树哈希处理出哪些子树同构。
如何判断两棵子树同构呢？
先给每个结点及其儿子构成的子树预处理出hash值。
深度相同并且hash值也相同的两个结点所构成的子树就是同构的两棵子树。
hash值可以利用double hashBy hiweibolu
具体地，构造这个 Hash 函数的方法是：
将子树内的所有节点按照 Hash 值从大到小排序，那么 Hash 函数为：
(h_{now}=size_{now}*sum h_{son_{now,i}}*seed^{i-1})
By OI Wiki 树哈希
dp,设f[x][y]表示子树x与子树y对应的最小代价。
为了找到dp转移时的代价，下面有两种做法：
方法1：
把x与y同构的儿子拎出来。
由于每个节点最多有11个儿子，所以考虑状压dp。
设g[s]表示x的前|s|个孩子对应y的孩子集合为s的最优解。
转移： g[s]+f[i][j] --> g[s+{j}]
方法2：
把同构的儿子连一条带权的边，跑km或最小费用最大流。（都不会）
tmd调了一整个晚上，期间一堆傻逼错误
放代码
//#pragma G++ optimize(3)
//#pragma GCC optimize(3)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define seed 1001
#define mod 1000000007
using namespace std;
int n,i,j,k,root,xx,yy,x,y,s,xxx,yyy,st,en,gg;
int a[1005],b[1005];
int l[2005],next[2005],last[1005],tot,size[1005],bz[1005];
int zx1,zx2,ma1,ma2;
int son[1005][20],height[1005];
int f[1005][1005],g[2080];
long long hash[1005];
int list[1005][1005];
int in[2080][12];
int status[12][2080];
void insert(int x,int y)
{
l[++tot]=y;
next[tot]=last[x];
last[x]=tot;
}
int comp(int x,int y)
{
return hash[x]<hash[y];
}
void find(int x)
{
int ma=0;
size[x]=1;
bz[x]=1;
for (int i=last[x];i>=1;i=next[i])
{
if (!bz[l[i]])
{
bz[l[i]]=1;
find(l[i]);
size[x]+=size[l[i]];
ma=max(ma,size[l[i]]);
}
}
ma=max(ma,n-size[x]);
if (ma<ma1)
{
zx1=x;
ma1=ma;
zx2=0;
ma2=0;
}
else
if (ma==ma1)
zx2=x,ma2=ma;
}
void build(int x)
{
size[x]=1;
bz[x]=1;
for (int i=last[x];i>=1;i=next[i])
{
if (!bz[l[i]])
{
son[x][++son[x][0]]=l[i];
height[l[i]]=height[x]+1;
bz[l[i]]=1;
build(l[i]);
size[x]+=size[l[i]];
}
}
sort(son[x]+1,son[x]+1+son[x][0],comp);
long long ss=1;
for (int i=1;i<=son[x][0];i++)
{
hash[x]=(hash[x]+hash[son[x][i]]*ss%mod)%mod;
ss=ss*seed%mod;
}
hash[x]=(ss*size[x])%mod;
}
int main()
{
freopen("read.in","r",stdin);
scanf("%d",&n);
for (i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
insert(x,y);
insert(y,x);
}
for (i=1;i<=n;i++)
scanf("%d",&a[i]);
for (i=1;i<=n;i++)
scanf("%d",&b[i]);
ma1=ma2=10000;
find(1);
if (zx2==0) root=zx1;
else
{
n++;
root=n;
for (i=last[zx1];i>=1;i=next[i])
if (l[i]==zx2) l[i]=n;
for (i=last[zx2];i>=1;i=next[i])
if (l[i]==zx1) l[i]=n;
insert(root,zx1);
insert(root,zx2);
}
memset(bz,0,sizeof(bz));
height[root]=1;
build(root);
for (i=1;i<=n;i++)
{
list[height[i]][0]++;
list[height[i]][list[height[i]][0]]=i;
}
for (i=0;i<=2047;i++)
{
for (j=1;j<=11;j++)
{
if ((i&(1<<(j-1)))!=0) in[i][j]=1;
}
}
for (i=0;i<=2047;i++)
{
s=0;
for (j=1;j<=11;j++)
{
if ((i&(1<<(j-1)))!=0) s++;
}
status[s][0]++;
status[s][status[s][0]]=i;
}
memset(f,120,sizeof(f));
for (k=n;k>=1;k--)
{
for (i=1;i<=list[k][0];i++)
{
for (j=1;j<=list[k][0];j++)
{
x=list[k][i];
y=list[k][j];
if (hash[x]!=hash[y]) continue;
for (gg=1;gg<=2047;gg++)
g[gg]=100000;
// memset(g,100,sizeof(g));
g[0]=0;
for (xx=1;xx<=son[x][0];xx++)
{
xxx=son[x][xx];
for (yy=1;yy<=son[y][0];yy++)
{
yyy=son[y][yy];
if (hash[xxx]==hash[yyy])
{
if ((yy==1)|(hash[xxx]!=hash[son[y][yy-1]])) st=yy;
if ((yy==son[y][0])|(hash[xxx]!=hash[son[y][yy+1]])) en=yy;
}
}
for (gg=status[xx-1][0];gg>=1;gg--)
{
s=status[xx-1][gg];
// for (s=(1<<(son[x][0]))-1;s>=0;s--)
// {
for (yy=st;yy<=en;yy++)
{
yyy=son[y][yy];
if (f[xxx][yyy]>10000) continue;
if (in[s][yy]) continue;
if (g[s]+f[xxx][yyy]<g[s+(1<<(yy-1))])
g[s+(1<<(yy-1))]=g[s]+f[xxx][yyy];
}
}
}
f[x][y]=g[(1<<son[x][0])-1];
if (a[x]!=b[y]) f[x][y]++;
}
}
}
printf("%d",f[root][root]);
}
T3
一眼计算几何，弃掉。
正解
对于一个点，我们求出可以不经过其他点的管辖范围的情况下可以到达哪些点。
把它与其他点的连线的垂直平分线求出来，求半平面交。
在半平面交上的线就是这个点能一步到达的。
连边，跑最短路。
题目好多改不完辣啊啊啊