QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#483053 | #5439. Meet in the Middle | Hadtsti | WA | 11ms | 37472kb | C++14 | 2.9kb | 2024-07-18 10:21:37 | 2024-07-18 10:21:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,q,x,y,z,ans[500010];
vector<pair<int,int> >Q[100010];
struct TREE
{
int fa[100010],dfn[100010],rk[100010],num,sz[100010],son[100010],d[100010],top[100010];
long long dis[100010];
vector<pair<int,int> >E[100010];
void dfs1(int x)
{
d[x]=d[fa[x]]+1;
sz[x]=1;
for(auto [y,z]:E[x])
if(y!=fa[x])
{
fa[y]=x;
dis[y]=dis[x]+z;
dfs1(y);
sz[x]+=sz[y];
if(sz[y]>sz[son[x]])
son[x]=y;
}
}
void dfs2(int x,int tp)
{
dfn[x]=++num;
rk[num]=x;
top[x]=tp;
if(!son[x])
return;
dfs2(son[x],tp);
for(auto [y,z]:E[x])
if(y!=son[x]&&y!=fa[x])
dfs2(y,y);
}
int LCA(int x,int y)
{
while(top[x]!=top[y])
{
if(d[top[x]]<d[top[y]])
swap(x,y);
x=fa[top[x]];
}
return d[x]<d[y]?x:y;
}
long long len(int x,int y)
{
return x&&y?dis[x]+dis[y]-2*dis[LCA(x,y)]:0;
}
}T1,T2;
struct path
{
struct point
{
int x;
long long dis;
}S,T;
long long dis;
path(point s={0,0},point t={0,0}){S=s,T=t,dis=T2.len(S.x,T.x)+S.dis+T.dis;}
friend bool operator <(path a,path b)
{
return a.dis<b.dis;
}
friend path operator +(path a,path b)
{
return max(max(max(a,b),max(path(a.S,b.S),path(a.T,b.T))),max(path(a.S,b.T),path(a.T,b.S)));
}
};
struct node
{
path P;
long long tag;
}tr[400010];
void addtag(int p,long long tag)
{
tr[p].P.S.dis+=tag;
tr[p].P.T.dis+=tag;
if(tr[p].P.T.x)
tr[p].P.dis+=2ll*tag;
tr[p].tag+=tag;
}
void pushdown(int p)
{
if(tr[p].tag)
{
addtag(p<<1,tr[p].tag);
addtag(p<<1|1,tr[p].tag);
tr[p].tag=0;
}
}
void build(int p=1,int l=1,int r=n)
{
if(l==r)
{
tr[p]={path({T1.rk[l],T1.dis[T1.rk[l]]}),0};
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tr[p].P=tr[p<<1].P+tr[p<<1|1].P;
}
void change(int p,int L,int R,long long v,int l=1,int r=n)
{
if(l>=L&&r<=R)
return addtag(p,v);
pushdown(p);
int mid=l+r>>1;
if(mid>=L)
change(p<<1,L,R,v,l,mid);
if(mid<R)
change(p<<1|1,L,R,v,mid+1,r);
tr[p].P=tr[p<<1].P+tr[p<<1|1].P;
}
void upd(int L,int R,long long v)
{
change(1,1,n,v);
change(1,L,R,-2ll*v);
}
long long ask(int x)
{
return max(T2.len(x,tr[1].P.S.x)+tr[1].P.S.dis,T2.len(x,tr[1].P.T.x)+tr[1].P.T.dis);
}
void calc(int x)
{
for(auto [y,z]:Q[x])
ans[z]=ask(y);
for(auto [y,z]:T1.E[x])
if(y!=T1.fa[x])
{
upd(T1.dfn[y],T1.dfn[y]+T1.sz[y]-1,z);
calc(y);
upd(T1.dfn[y],T1.dfn[y]+T1.sz[y]-1,-z);
}
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
T1.E[x].push_back({y,z});
}
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&z);
T2.E[x].push_back({y,z});
}
T1.dfs1(1);
T1.dfs2(1,0);
T2.dfs1(1);
T2.dfs2(1,0);
build();
for(int i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
Q[x].push_back({y,i});
}
calc(1);
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 33992kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
6 4 5 3
result:
ok 4 number(s): "6 4 5 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 33980kb
input:
2 1 1 2 1 1 2 1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 36372kb
input:
2 1 1 2 1 1 2 1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Wrong Answer
time: 11ms
memory: 37472kb
input:
10000 50000 8101 5996 108427744 5996 7605 870838849 5996 5599 603303696 8101 3006 339377417 8101 6463 442516687 6463 5560 109174079 5560 4063 127596224 3006 1682 947915262 5996 1986 130416311 6463 5455 279771516 6463 2634 516688796 4063 3034 217886863 7605 5092 742375061 5599 2266 193804402 5092 140...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '0'