# 為什麼出錯了？（已解決）

https://vijos.org/discuss/598482f9d3d8a17a62bbde2d#1603289438
/in/foo.cc: In function 'void dts::tr_dfs1(int, int, int)':
/in/foo.cc:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~
/in/foo.cc: In function 'void dts::tr_dfs2(int, int)':
/in/foo.cc:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~

# 狀態 耗時 記憶體佔用

#1 Wrong Answer 15ms 26.801 MiB
#2 Wrong Answer 16ms 26.789 MiB
#3 Wrong Answer 15ms 27.148 MiB
#4 Wrong Answer 268ms 30.406 MiB
#5 Wrong Answer 267ms 30.305 MiB
#6 Wrong Answer 266ms 30.41 MiB
#7 Wrong Answer 263ms 30.371 MiB
#8 Wrong Answer 405ms 34.035 MiB
#9 Wrong Answer 402ms 34.023 MiB
#10 Wrong Answer 364ms 33.969 MiB

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

namespace dts
{
int ft=1,cnt;
class tree_node
{
public:
int fa,dep,size,hs,top,id;
vector<int> s;
};
int rk[(1<<17)+1];
tree_node tr[(1<<17)+1];
void tr_dfs1(int now,int fa,int dep)
{
tr[now].fa=fa;
tr[now].dep=dep;
tr[now].size=1;
tr[now].hs=-1;
for (int i=0;i<tr[now].s.size();i++)
if (tr[now].s[i]!=fa)
{
int next=tr[now].s[i];
tr_dfs1(next,now,dep+1);
tr[now].size+=tr[next].size;
if (tr[now].hs==-1)
tr[now].hs=next;
else if (tr[tr[now].hs].size<tr[next].size)
tr[now].hs=next;
}
}
void tr_dfs2(int now,int top)
{
tr[now].top=top;
tr[now].id=++cnt;
rk[cnt]=now;
if (tr[now].hs!=-1)
{
tr_dfs2(tr[now].hs,top);
for (int i=0;i<tr[now].s.size();i++)
if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
tr_dfs2(tr[now].s[i],tr[now].s[i]);
}
}
void tr_build()
{
cnt=0;
tr_dfs1(ft,ft,1);
tr_dfs2(ft,ft);
}
int lca(int x,int y)
{
while (tr[x].top!=tr[y].top)
{
if (tr[tr[x].top].dep<tr[tr[y].top].dep)
swap(x,y);
x=tr[tr[x].top].fa;
}
if (tr[x].dep<tr[y].dep)
return x;
else
return y;
}

class st_node
{
public:
int l,r,mid,empt=1;
int lans=0,rans=0,ans=0,sum=0;
int iflz=0,numlz;
int len()
{
return tr[r].dep-tr[l].dep+1;
}
};
int data[(1<<17)+1];
st_node st[(1<<19)+2];
#define lc(now) ((now)<<1)
#define rc(now) ((now)<<1|1)
st_node merge(st_node li,st_node ri)//li:左子區間，ri:右子區間
{
if (li.empt)
return ri;
else if (ri.empt)
return li;
st_node a;
a.empt=a.iflz=0;
a.l=li.l,a.r=ri.r,a.mid=li.r;
a.lans=max(li.lans,li.sum+ri.lans);
a.rans=max(ri.rans,ri.sum+li.rans);
a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
a.sum=li.sum+ri.sum;
return a;
}
void st_pushup(int now)
{
st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
}
void st_update(int now,int l,int r,int val);
void st_pushdown(int now)
{
if (st[now].iflz)
{
st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
st[now].iflz=0;
}
}
void st_update(int now,int l,int r,int val)
{
if (st[now].l==l&&r==st[now].r)
{
st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
st[now].sum=st[now].len()*val;
st[now].iflz=1,st[now].numlz=val;
}
else
{
st_pushdown(now);
if (r<=st[now].mid)
st_update(lc(now),l,r,val);
else if (st[now].mid+1<=l)
st_update(rc(now),l,r,val);
else
st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
st_pushup(now);
}
}
{
if (st[now].l==l&&r==st[now].r)
return st[now];
else
{
st_pushdown(now);
if (r<=st[now].mid)
else if (st[now].mid+1<=l)
else
}
}
void st_build(int now,int l,int r)
{
st[now].empt=st[now].iflz=0;
st[now].l=l,st[now].r=r;
if (l<r)
{
st[now].mid=(l+r)>>1;
st_build(lc(now),l,st[now].mid);
st_build(rc(now),st[now].mid+1,r);
st_pushup(now);
}
else
{
st[now].sum=data[rk[l]];
st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
}
}

void update(int x,int y,int val)
{
int i,j,lcan=lca(x,y);
for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
st_update(1,tr[tr[i].top].id,tr[i].id,val);
for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
st_update(1,tr[tr[j].top].id,tr[j].id,val);
if (tr[i].dep>tr[j].dep)
swap(i,j);
st_update(1,tr[i].id,tr[j].id,val);
}
st_node cty(st_node stn)
{
swap(stn.l,stn.r);
swap(stn.lans,stn.rans);
return stn;
}
{
int i,j,lcan=lca(x,y);
st_node ians,jans,ans;
ians.iflz=jans.iflz=0;
ians.empt=jans.empt=1;
for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
if (tr[i].dep>tr[j].dep)
swap(i,j),swap(ians,jans);
ans=merge(cty(jans),ians);
return ans.ans;
}

int n,m;

void main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&data[i]);
for (int i=1;i<=n;i++)
tr[i].s.clear();
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
tr[x].s.push_back(y);
tr[y].s.push_back(x);
}
if (n>0)
tr_build();
st_build(1,1,cnt);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int K,x,y;
scanf("%d%d%d",&K,&x,&y);
if (K==1)
else if (K==2)
{
int val;
scanf("%d",&val);
update(x,y,val);
}
}
printf("\n");
}
}

int main()
{
dts::main();
}
``````

# 3 条评论

• @ 2020-10-23 01:10:51

找出問題了：
正確方式：

``````    class st_node
{
public:
int l,r,mid,empt=1;
int lans=0,rans=0,ans=0,sum=0;
int iflz=0,numlz;
int len()
{
return tr[rk[r]].dep-tr[rk[l]].dep+1;
}
};
``````

完整代碼：

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

namespace dts
{
int ft=1,cnt;
class tree_node
{
public:
int fa,dep,size,hs,top,id;
vector<int> s;
};
int rk[(1<<17)+1];
tree_node tr[(1<<17)+1];
void tr_dfs1(int now,int fa,int dep)
{
tr[now].fa=fa;
tr[now].dep=dep;
tr[now].size=1;
tr[now].hs=-1;
for (int i=0;i<tr[now].s.size();i++)
if (tr[now].s[i]!=fa)
{
int next=tr[now].s[i];
tr_dfs1(next,now,dep+1);
tr[now].size+=tr[next].size;
if (tr[now].hs==-1)
tr[now].hs=next;
else if (tr[tr[now].hs].size<tr[next].size)
tr[now].hs=next;
}
}
void tr_dfs2(int now,int top)
{
tr[now].top=top;
tr[now].id=++cnt;
rk[cnt]=now;
if (tr[now].hs!=-1)
{
tr_dfs2(tr[now].hs,top);
for (int i=0;i<tr[now].s.size();i++)
if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
tr_dfs2(tr[now].s[i],tr[now].s[i]);
}
}
void tr_build()
{
cnt=0;
tr_dfs1(ft,ft,1);
tr_dfs2(ft,ft);
}
int lca(int x,int y)
{
while (tr[x].top!=tr[y].top)
{
if (tr[tr[x].top].dep<tr[tr[y].top].dep)
swap(x,y);
x=tr[tr[x].top].fa;
}
if (tr[x].dep<tr[y].dep)
return x;
else
return y;
}

class st_node
{
public:
int l,r,mid,empt=1;
int lans=0,rans=0,ans=0,sum=0;
int iflz=0,numlz;
int len()
{
return tr[rk[r]].dep-tr[rk[l]].dep+1;
}
};
int data[(1<<17)+1];
st_node st[(1<<19)+2];
#define lc(now) ((now)<<1)
#define rc(now) ((now)<<1|1)
st_node merge(st_node li,st_node ri)//li:左子區間，ri:右子區間
{
if (li.empt)
return ri;
else if (ri.empt)
return li;
st_node a;
a.empt=a.iflz=0;
a.l=li.l,a.r=ri.r,a.mid=li.r;
a.lans=max(li.lans,li.sum+ri.lans);
a.rans=max(ri.rans,ri.sum+li.rans);
a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
a.sum=li.sum+ri.sum;
return a;
}
void st_pushup(int now)
{
st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
}
void st_update(int now,int l,int r,int val);
void st_pushdown(int now)
{
if (st[now].iflz)
{
st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
st[now].iflz=0;
}
}
void st_update(int now,int l,int r,int val)
{
if (st[now].l==l&&r==st[now].r)
{
st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
st[now].sum=st[now].len()*val;
st[now].iflz=1,st[now].numlz=val;
}
else
{
st_pushdown(now);
if (r<=st[now].mid)
st_update(lc(now),l,r,val);
else if (st[now].mid+1<=l)
st_update(rc(now),l,r,val);
else
st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
st_pushup(now);
}
}
{
if (st[now].l==l&&r==st[now].r)
return st[now];
else
{
st_pushdown(now);
if (r<=st[now].mid)
else if (st[now].mid+1<=l)
else
}
}
void st_build(int now,int l,int r)
{
st[now].empt=st[now].iflz=0;
st[now].l=l,st[now].r=r;
if (l<r)
{
st[now].mid=(l+r)>>1;
st_build(lc(now),l,st[now].mid);
st_build(rc(now),st[now].mid+1,r);
st_pushup(now);
}
else
{
st[now].sum=data[rk[l]];
st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
}
}

void update(int x,int y,int val)
{
int i,j,lcan=lca(x,y);
for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
st_update(1,tr[tr[i].top].id,tr[i].id,val);
for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
st_update(1,tr[tr[j].top].id,tr[j].id,val);
if (tr[i].dep>tr[j].dep)
swap(i,j);
st_update(1,tr[i].id,tr[j].id,val);
}
st_node cty(st_node stn)
{
swap(stn.l,stn.r);
swap(stn.lans,stn.rans);
return stn;
}
{
int i,j,lcan=lca(x,y);
st_node ians,jans,ans;
ians.iflz=jans.iflz=0;
ians.empt=jans.empt=1;
for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
if (tr[i].dep>tr[j].dep)
swap(i,j),swap(ians,jans);
ans=merge(cty(jans),ians);
return ans.ans;
}

int n,m;

void main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&data[i]);
for (int i=1;i<=n;i++)
tr[i].s.clear();
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
tr[x].s.push_back(y);
tr[y].s.push_back(x);
}
if (n>0)
tr_build();
st_build(1,1,cnt);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int K,x,y;
scanf("%d%d%d",&K,&x,&y);
if (K==1)
else if (K==2)
{
int val;
scanf("%d",&val);
update(x,y,val);
}
}
printf("\n");
}
}

int main()
{
dts::main();
}
``````
• @ 2020-10-22 22:14:13

為什麼區間長度不能用深度計算？
這是錯誤的：

``````    class st_node
{
public:
int l,r,mid,empt=1;
int lans=0,rans=0,ans=0,sum=0;
int iflz=0,numlz;
int len()
{
return tr[r].dep-tr[l].dep+1;
}
};
``````

這是正確的：

``````    class st_node
{
public:
int l,r,mid,empt=1;
int lans=0,rans=0,ans=0,sum=0;
int iflz=0,numlz;
int len()
{
return r-l+1;
}
};
``````
• @ 2020-10-23 09:36:20

用深度計算（正確方式）：

``````    class st_node
{
public:
int l,r,mid,empt=1;
int lans=0,rans=0,ans=0,sum=0;
int iflz=0,numlz;
int len()
{
return tr[rk[r]].dep-tr[rk[l]].dep+1;
}
};

``````
• @ 2020-10-22 22:12:24

剛才AC了
Accepted
/in/foo.cc: In function 'void dts::tr_dfs1(int, int, int)':
/in/foo.cc:28:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~
/in/foo.cc: In function 'void dts::tr_dfs2(int, int)':
/in/foo.cc:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0;i<tr[now].s.size();i++)
~^~~~~~~~~~~~~~~~~

# 狀態 耗時 記憶體佔用

#1 Accepted 16ms 26.785 MiB
#2 Accepted 15ms 26.789 MiB
#3 Accepted 15ms 26.785 MiB
#4 Accepted 168ms 30.414 MiB
#5 Accepted 163ms 30.312 MiB
#6 Accepted 166ms 30.344 MiB
#7 Accepted 166ms 30.336 MiB
#8 Accepted 356ms 34.043 MiB
#9 Accepted 359ms 33.945 MiB
#10 Accepted 335ms 33.965 MiB

``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
using namespace std;

namespace dts
{
int ft=1,cnt;
class tree_node
{
public:
int fa,dep,size,hs,top,id;
vector<int> s;
};
int rk[(1<<17)+1];
tree_node tr[(1<<17)+1];
void tr_dfs1(int now,int fa,int dep)
{
tr[now].fa=fa;
tr[now].dep=dep;
tr[now].size=1;
tr[now].hs=-1;
for (int i=0;i<tr[now].s.size();i++)
if (tr[now].s[i]!=fa)
{
int next=tr[now].s[i];
tr_dfs1(next,now,dep+1);
tr[now].size+=tr[next].size;
if (tr[now].hs==-1)
tr[now].hs=next;
else if (tr[tr[now].hs].size<tr[next].size)
tr[now].hs=next;
}
}
void tr_dfs2(int now,int top)
{
tr[now].top=top;
tr[now].id=++cnt;
rk[cnt]=now;
if (tr[now].hs!=-1)
{
tr_dfs2(tr[now].hs,top);
for (int i=0;i<tr[now].s.size();i++)
if (tr[now].s[i]!=tr[now].fa&&tr[now].s[i]!=tr[now].hs)
tr_dfs2(tr[now].s[i],tr[now].s[i]);
}
}
void tr_build()
{
cnt=0;
tr_dfs1(ft,ft,1);
tr_dfs2(ft,ft);
}
int lca(int x,int y)
{
while (tr[x].top!=tr[y].top)
{
if (tr[tr[x].top].dep<tr[tr[y].top].dep)
swap(x,y);
x=tr[tr[x].top].fa;
}
if (tr[x].dep<tr[y].dep)
return x;
else
return y;
}

class st_node
{
public:
int l,r,mid,empt=1;
int lans=0,rans=0,ans=0,sum=0;
int iflz=0,numlz;
int len()
{
return r-l+1;
}
};
int data[(1<<17)+1];
st_node st[(1<<19)+2];
#define lc(now) ((now)<<1)
#define rc(now) ((now)<<1|1)
st_node merge(st_node li,st_node ri)//li:左子區間，ri:右子區間
{
if (li.empt)
return ri;
else if (ri.empt)
return li;
st_node a;
a.empt=a.iflz=0;
a.l=li.l,a.r=ri.r,a.mid=li.r;
a.lans=max(li.lans,li.sum+ri.lans);
a.rans=max(ri.rans,ri.sum+li.rans);
a.ans=max(max(li.ans,ri.ans),li.rans+ri.lans);
a.sum=li.sum+ri.sum;
return a;
}
void st_pushup(int now)
{
st[now]=merge(st[lc(now)],st[rc(now)]);//別在意時間複雜度常數
}
void st_update(int now,int l,int r,int val);
void st_pushdown(int now)
{
if (st[now].iflz)
{
st_update(lc(now),st[now].l,st[now].mid,st[now].numlz);
st_update(rc(now),st[now].mid+1,st[now].r,st[now].numlz);
st[now].iflz=0;
}
}
void st_update(int now,int l,int r,int val)
{
if (st[now].l==l&&r==st[now].r)
{
st[now].lans=st[now].rans=st[now].ans=max(st[now].len()*val,0);
st[now].sum=st[now].len()*val;
st[now].iflz=1,st[now].numlz=val;
}
else
{
st_pushdown(now);
if (r<=st[now].mid)
st_update(lc(now),l,r,val);
else if (st[now].mid+1<=l)
st_update(rc(now),l,r,val);
else
st_update(lc(now),l,st[now].mid,val),st_update(rc(now),st[now].mid+1,r,val);
st_pushup(now);
}
}
{
if (st[now].l==l&&r==st[now].r)
return st[now];
else
{
st_pushdown(now);
if (r<=st[now].mid)
else if (st[now].mid+1<=l)
else
}
}
void st_build(int now,int l,int r)
{
st[now].empt=st[now].iflz=0;
st[now].l=l,st[now].r=r;
if (l<r)
{
st[now].mid=(l+r)>>1;
st_build(lc(now),l,st[now].mid);
st_build(rc(now),st[now].mid+1,r);
st_pushup(now);
}
else
{
st[now].sum=data[rk[l]];
st[now].lans=st[now].rans=st[now].ans=max(data[rk[l]],0);
}
}

void update(int x,int y,int val)
{
int i,j,lcan=lca(x,y);
for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
st_update(1,tr[tr[i].top].id,tr[i].id,val);
for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
st_update(1,tr[tr[j].top].id,tr[j].id,val);
if (tr[i].dep>tr[j].dep)
swap(i,j);
st_update(1,tr[i].id,tr[j].id,val);
}
st_node cty(st_node stn)
{
swap(stn.l,stn.r);
swap(stn.lans,stn.rans);
return stn;
}
{
int i,j,lcan=lca(x,y);
st_node ians,jans,ans;
ians.iflz=jans.iflz=0;
ians.empt=jans.empt=1;
for (i=x;tr[i].top!=tr[lcan].top;i=tr[tr[i].top].fa)
for (j=y;tr[j].top!=tr[lcan].top;j=tr[tr[j].top].fa)
if (tr[i].dep>tr[j].dep)
swap(i,j),swap(ians,jans);
ans=merge(cty(jans),ians);
return ans.ans;
}

int n,m;

void main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&data[i]);
for (int i=1;i<=n;i++)
tr[i].s.clear();
for (int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
tr[x].s.push_back(y);
tr[y].s.push_back(x);
}
if (n>0)
tr_build();
st_build(1,1,cnt);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
int K,x,y;
scanf("%d%d%d",&K,&x,&y);
if (K==1)
else if (K==2)
{
int val;
scanf("%d",&val);
update(x,y,val);
}
}
printf("\n");
}
}

int main()
{
dts::main();
}
``````
• 1

ID
1620

8

(无)

809

111

14%