惯例开坑。
任务栏：
订正了几题？2/3
BZOJ刷题量？288/300
还有11天就要ZJOIDay1了苯宝宝好虚啊。
（诶我的博客画风为啥变得这么正常了）
T1
谜之声：蛤？原来暴力就是正解？
给定一棵二叉树，可以付出wi的代价，给叶子i加1的权值；对于非叶子节点，若左子树的权值和为x，右子树的权值和为y，则代价为wi*(x^y)。求出给树加权分别为1,2,3，……，n时的最小代价。
令dp[i][j]表示i及i的子树中加权为j时的最小代价，暴力枚举左右子树转移，通过势能分析可知这种做法是n2的。
T2
谜之声：神之数学题。。。
由于此题太难，只能以后再填坑了。
T3
谜之声：此题需要实现dfs、Dfs、DFs、DFS、dFs以及dFS……
给你一棵树，对于每个点，求经过这个点的边权异或值最大的简单路径。
trie即视感。。。
然后窝就喜闻乐见地打了50分暴力。。。
考虑点分治，对于每棵子树到分治重心的路径边权异或值建一棵trie，每次枚举子树，先利用贪心性质在trie上询问得出一条经过分治重心最优路径，并对路径上的点更新一下，然后再合并。
不算黑科技的黑科技1：正反两边枚举子树来保证能更新到两个端点。
不算黑科技的黑科技2：对于路径上的更新，不需要写树链剖分，先更新端点然后做一次子树最大值即可。
然而这并不能改变此题的码农性质。。。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=10010;
const int inf=2000000000;
int cas,n,i,j;
int l[M],r[M],isroot[M],size[M],w[M],dp[4010][4010];
void dfs(int u){
dp[u][0]=0;
if (!l[u]&&!r[u]){size[u]=1;dp[u][1]=w[u];return;}
dfs(l[u]);
dfs(r[u]);
size[u]+=size[l[u]]+size[r[u]];
for (int i=0;i<=size[l[u]];i++)
for (int j=0;j<=size[r[u]];j++)
dp[u][i+j]=min(dp[u][i+j],dp[l[u]][i]+dp[r[u]][j]+w[u]*(i^j));
}
int main(){
scanf("%d",&cas);
while (cas--){
memset(isroot,0,sizeof isroot);
memset(size,0,sizeof size);
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%d%d",&l[i],&r[i]);
isroot[l[i]]=1;
isroot[r[i]]=1;
}
for (i=1;i<=n;i++)scanf("%d",&w[i]);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)dp[i][j]=inf;
for (i=1;i<=n;i++)
if (!isroot[i]){
dfs(i);
for (j=1;j<size[i];j++)printf("%d ",dp[i][j]);
printf("%d\n",dp[i][size[i]]);
break;
}
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=200010;
const int inf=1000000007;
int n,i,x,y,z,edgenum,sum,root,pointnum,top,num;
int head[M],vet[M],next[M],len[M],flag[M],size[M],mx[M],ans[M],Ans[M],seq[M][2],a[M][2],trie[M*20][2];
void addedge(int x,int y,int z){
vet[++edgenum]=y;
next[edgenum]=head[x];
head[x]=edgenum;
len[edgenum]=z;
}
void addtrie(int x){
int u=0,p;
for (int i=30;i>=0;i--){
if (x&(1<<i))p=1;else p=0;
if (!trie[u][p])trie[u][p]=++pointnum;
u=trie[u][p];
}
}
void update(int x,int y){
int u=0,w=0,p;
for (int i=30;i>=0;i--){
if (x&(1<<i))p=0;else p=1;
if (!trie[u][p])u=trie[u][p^1];
else{w+=1<<i;u=trie[u][p];}
}
Ans[y]=max(Ans[y],w);
}
void getroot(int u,int fa){
size[u]=1;mx[u]=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (v==fa||flag[v])continue;
getroot(v,u);
size[u]+=size[v];
mx[u]=max(mx[u],size[v]);
}
mx[u]=max(mx[u],sum-size[u]);
if (mx[u]<mx[root])root=u;
}
void dfs(int u,int fa,int w){
top++;a[top][0]=w;a[top][1]=u;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (v==fa||flag[v])continue;
dfs(v,u,w^len[e]);
}
}
void Dfs(int u,int fa){
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (v==fa||flag[v])continue;
Dfs(v,u);
Ans[u]=max(Ans[u],Ans[v]);
}
}
void DFS(int u,int fa){
ans[u]=max(ans[u],Ans[u]);
Ans[u]=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (v==fa||flag[v])continue;
DFS(v,u);
}
}
void solve(int u){
flag[u]=1;num=0;
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (flag[v])continue;
seq[++num][0]=v;seq[num][1]=len[e];
}
for (int i=0;i<=pointnum;i++)trie[i][0]=trie[i][1]=0;
pointnum=0;addtrie(0);
for (int j=1;j<=num;j++){
top=0;
dfs(seq[j][0],-1,seq[j][1]);
for (int i=1;i<=top;i++)update(a[i][0],a[i][1]);
for (int i=1;i<=top;i++)addtrie(a[i][0]);
}
for (int i=0;i<=pointnum;i++)trie[i][0]=trie[i][1]=0;
pointnum=0;addtrie(0);
for (int j=num;j;j--){
top=0;
dfs(seq[j][0],-1,seq[j][1]);
for (int i=1;i<=top;i++)update(a[i][0],a[i][1]);
for (int i=1;i<=top;i++)addtrie(a[i][0]);
}
Dfs(u,-1);
DFS(u,-1);
for (int e=head[u];e;e=next[e]){
int v=vet[e];
if (flag[v])continue;
mx[root=0]=inf;
sum=size[v];
getroot(v,-1);
solve(root);
}
}
int main(){
scanf("%d",&n);
for (i=1;i<n;i++){
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
mx[root=0]=inf;
sum=n;
getroot(1,-1);
solve(root);
for (i=1;i<=n;i++)printf("%d\n",ans[i]);
}
对于上一篇滚粗记坑人的行为，我表示诚挚的歉意。
如果你接受了窝的道歉，请欣赏下面这张图片：
按Ctrl+A还有一张（如果你接受了窝的道歉，那你就真的是SB了）
评论 (0)
