传奇英雄 @ 2020-05-18 09:54:09
我写的是正解啊！正解的点分治，而且是m个询问一起处理的。O2已开。T2个点。
https://www.luogu.com.cn/record/33688812
T了n次了，死活没发过。。
by FZzzz @ 2020-05-18 10:25:56
用 memset 那你复杂度肯定假了
by 传奇英雄 @ 2020-05-18 10:26:15
好了，我晚上再调一下。
by FZzzz @ 2020-05-18 10:27:37
@传奇英雄 你倒是放出来看看啊……我们都不知道你是怎么写的你就说这题卡常那不是扯吗……
by 传奇英雄 @ 2020-05-18 14:08:02
@FZzzz 我放了啊，你们看不见我代码么？
by 传奇英雄 @ 2020-05-18 14:09:45
#include <bits/stdc++.h>
using namespace std;
const int g=10005,h=20005;
int n,m,xx,yy,zz,x[h],y[h],z[g],w[h],s,a[g];
int d[g],dp[g],dd[g],u,v,e,m1,fa,cnt,l,r,sum;
bool f[g],f2[g],fl[g];
pair<int,int> b[g];
inline int read()
{
int F=1,Num=0; //F是记录数字是否为负数，Num存储读入的数字
char ch=getchar(); //getchar()读取一个字符
while(!isdigit(ch)) //isdigit()判断是否为数字
{
if(ch=='-') F=-1; //如果读入的字符是符号，标记F
ch=getchar(); //继续读字符
}
while(isdigit(ch)) //如果当前读入的字符是数字，则将整个数字全部读入
{
Num=Num*10+ch-'0'; //将读入的ASCII字符转换为数字
//或者上面的代码可以这样写:Num=(Num<<1)+(Num<<3)+ch-'0';
ch=getchar(); //读取下一个字符
}
return Num*F; //将读取完毕的字符返回
}
void get(int xx,int yy)
{
x[++s]=z[xx];
y[s]=yy;
z[xx]=s;
w[s]=zz;
}
void dfs(int t)//找重心
{
f2[t]=1;
dp[t]=1,dd[t]=0;
for(int i=z[t];i;i=x[i])
if(!f2[y[i]]&&!f[y[i]])
{
dfs(y[i]);
dp[t]+=dp[y[i]];
dd[t]=max(dd[t],dd[y[i]]+1);
}
m1=max(dd[t],e-dd[t]-1);
if(m1<u) u=m1,v=t;
}
void dfs2(int t)
{
m1=max(dd[t],e-dd[t]-1);
if(m1<u) u=m1,v=t;
for(int i=z[t];i;i=x[i])
if(dp[y[i]]<dp[t]&&!f[y[i]])
dfs2(y[i]);
}
void d2(int t)
{
b[++cnt].first=d[t];
b[cnt].second=fa;
for(int i=z[t];i;i=x[i])
if(!d[y[i]]&&!f[y[i]])
{
d[y[i]]=d[t]+w[i];
d2(y[i]);
}
}
void find(int t)
{
f[v]=1;
cnt=1;
b[1].first=0;
b[1].second=v;
memset(d,0,sizeof(d));
for(int i=z[v];i;i=x[i])
if(!f[y[i]])
{
fa=y[i];
d[y[i]]=w[i];
d2(y[i]);
}
sort(b+2,b+cnt+1);
for(int i=1;i<=m;i++)
if(!fl[i]&&b[1].first+b[2].first<=a[i]&&b[n].first+b[n-1].first>=a[i])
{
l=1,m1=a[i]-b[1].first;
for(int j=0;j>=0;)
{
r=l+(1<<j);
if(r>cnt||b[r].first>m1) j--;
else
{
l=r;
j++;
}
}
if(b[l].first==m1)
for(int j=l;b[j].first==b[l].first;j++)
if(b[1].second!=b[j].second)
{
fl[i]=1;
sum++;
if(sum==m)
{
for(int i=1;i<=m;i++)
printf("AYE\n");
exit(0);
}
break;
}
if(!fl[i])
for(int j=2;j<=cnt;j++)
{
m1=a[i]-b[j].first;
for(;b[l-1].first>=m1;l--)
if(l<=j+1) break;
if(b[l].first==m1)
for(r=l;b[r].first==b[l].first;r++)
if(b[j].second!=b[r].second)
{
fl[i]=1;
sum++;
if(sum==m)
{
for(int i=1;i<=m;i++)
printf("AYE\n");
exit(0);
}
break;
}
if(fl[i]||l<=j+1) break;
}
}
int m2=v;
for(int i=z[m2];i;i=x[i])
if(!f[y[i]])
{
if(dp[y[i]]<dp[m2])
{
e=dp[y[i]],u=n;
dfs2(y[i]);
}
else
{
e=dp[t]-dp[m2],u=n;
memset(f2,0,sizeof(f2));
dfs(y[i]);
}
find(v);
}
}
int main()
{
//freopen("in","r",stdin);
//scanf("%d%d",&n,&m);
n = read(), m = read();
for(int i=1;i<n;i++)
{
//scanf("%d%d%d",&xx,&yy,&zz);
xx = read(), yy = read(), zz = read();
get(xx,yy);
get(yy,xx);
}
for(int i=1;i<=m;i++) a[i] = read();
//scanf("%d",&a[i]);
e=u=n;//e为子树总大小
dfs(1);
find(1);
for(int i=1;i<=m;i++)
if(fl[i]) printf("AYE\n");
else printf("NAY\n");
return 0;
}by FZzzz @ 2020-05-18 14:15:29
@传奇英雄 您这种重心的找法感觉有一点问题……但是不知道会不会导致复杂度假掉
您先把这个 memset 换掉，一次 memset 是
by 传奇英雄 @ 2020-05-18 16:09:28
@FZzzz 嗯嗯，正在改。是我的错。。。
by woshiren @ 2020-05-18 18:20:14
我也惨被卡了
7和10，T飞了
如果楼主有办法解决，希望能告诉我
by 传奇英雄 @ 2020-05-18 19:23:02
@FZzzz 不对啊，我改了还是T飞？而且第7组数据在本地能过，要跑0.3秒左右。
by 传奇英雄 @ 2020-05-18 19:23:58
改了的代码
#include <bits/stdc++.h>
using namespace std;
const int g=10005,h=20005;
int n,m,xx,yy,zz,x[h],y[h],z[g],w[h],s,a[g];
int d[g],dp[g],dd[g],u,v,e,m1,fa,sum,big;
int b[g],cnt;
bool f[g],f2[g],fl[g],f3[10000005];
inline int read()
{
int F=1,Num=0; //F是记录数字是否为负数，Num存储读入的数字
char ch=getchar(); //getchar()读取一个字符
while(!isdigit(ch)) //isdigit()判断是否为数字
{
if(ch=='-') F=-1; //如果读入的字符是符号，标记F
ch=getchar(); //继续读字符
}
while(isdigit(ch)) //如果当前读入的字符是数字，则将整个数字全部读入
{
Num=Num*10+ch-'0'; //将读入的ASCII字符转换为数字
//或者上面的代码可以这样写:Num=(Num<<1)+(Num<<3)+ch-'0';
ch=getchar(); //读取下一个字符
}
return Num*F; //将读取完毕的字符返回
}
void get(int xx,int yy)
{
x[++s]=z[xx];
y[s]=yy;
z[xx]=s;
w[s]=zz;
}
void dfs(int t)//找重心
{
f2[t]=1;
dp[t]=1,dd[t]=0;
for(int i=z[t];i;i=x[i])
if(!f2[y[i]]&&!f[y[i]])
{
dfs(y[i]);
dp[t]+=dp[y[i]];
dd[t]=max(dd[t],dd[y[i]]+1);
}
m1=max(dd[t],e-dd[t]-1);
if(m1<u) u=m1,v=t;
}
void dfs2(int t)
{
m1=max(dd[t],e-dd[t]-1);
if(m1<u) u=m1,v=t;
for(int i=z[t];i;i=x[i])
if(dp[y[i]]<dp[t]&&!f[y[i]])
dfs2(y[i]);
}
void d2(int t)
{
b[++cnt]=d[t];
for(int i=z[t];i;i=x[i])
if(!d[y[i]]&&!f[y[i]])
{
d[y[i]]=d[t]+w[i];
if(d[y[i]]<=big) d2(y[i]);
}
}
void find(int t)
{
f[v]=1;
cnt=1;
memset(d,0,sizeof(d));
int m2;
for(int i=z[v];i;i=x[i])
{
m2=cnt+1;
if(!f[y[i]])
{
fa=y[i];
d[y[i]]=w[i];
d2(y[i]);
}
for(int k=1;k<=m;k++)
if(!fl[k])
{
for(int j=m2;j<=cnt;j++)
if(a[k]>=b[j])
if(f3[a[k]-b[j]])
{
fl[k]=1;
sum++;
if(sum==m)
{
for(int ac=1;ac<=m;ac++)
printf("AYE\n");
exit(0);
}
break;
}
}
for(int j=m2;j<=cnt;j++)
f3[b[j]]=1;
}
for(int i=2;i<=cnt;i++)
f3[b[i]]=0;
m2=v;
for(int i=z[m2];i;i=x[i])
if(!f[y[i]])
{
if(dp[y[i]]<dp[m2])
{
e=dp[y[i]],u=n;
dfs2(y[i]);
}
else
{
e=dp[t]-dp[m2],u=n;
memset(f2,0,sizeof(f2));
dfs(y[i]);
}
find(v);
}
}
int main()
{
//freopen("in","r",stdin);
//freopen("out","w",stdout);
//scanf("%d%d",&n,&m);
n = read(), m = read();
for(int i=1;i<n;i++)
{
//scanf("%d%d%d",&xx,&yy,&zz);
xx = read(), yy = read(), zz = read();
get(xx,yy);
get(yy,xx);
}
for(int i=1;i<=m;i++)
{
//scanf("%d",&a[i]);
a[i] = read();
big=max(big,a[i]);
}
e=u=n;//e为子树总大小
dfs(1);
f3[0]=1;
find(1);
for(int i=1;i<=m;i++)
if(fl[i]) printf("AYE\n");
else printf("NAY\n");
return 0;
}