QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#692303 | #5439. Meet in the Middle | Daniel777 | WA | 5ms | 25896kb | C++14 | 3.2kb | 2024-10-31 14:17:49 | 2024-10-31 14:17:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
typedef long long ll;
const int N = 1e5+5,M = 5e5+5;
vector< pii >tr1[N],tr2[N];
int n,m;
int A[M],B[M];
vector<int>q[N];
int dfn[N],rk[N<<1],dfcnt;
ll st[20][N<<1];
ll sum[N],ans[M];
ll cur[N];
int sz[N],rt,vis[N];
int cx,cy;
void dfs(int u,int fa)
{
rk[dfn[u] = ++dfcnt] = u;
for(auto [v,w]:tr2[u]) if(v != fa)
{
sum[v] = sum[u] + w;
dfs(v,u);
rk[++dfcnt] = u;
}
}
ll Dist(int x,int y)
{
int l = dfn[x],r = dfn[y];
if(l > r) swap(l,r);
int t = __lg(r-l+1);
return sum[x] + sum[y] - 2*min(st[t][l],st[t][r-(1<<t)+1]);
}
void getrt(int u,int fa,int SZ)
{
int mx = 0;
sz[u] = 1;
for(auto [v,w]:tr1[u]) if(v != fa && !vis[v])
{
getrt(v,u,SZ);
sz[u] += sz[v];
mx = max(mx,sz[v]);
}
mx = max(mx,SZ-sz[u]);
if(mx*2 <= SZ) rt = u;
}
void qry(int u,int fa)
{
for(auto id:q[u]) ans[id] = max(ans[id],max(Dist(cx,B[id])+cur[cx],Dist(cy,B[id])+cur[cy])+cur[u]);
for(auto [v,w]:tr1[u]) if(v != fa && !vis[v]) qry(v,u);
}
void updt(int u,int fa)
{
ll d1 = cur[cx] + cur[cy] + Dist(cx,cy);
ll d2 = cur[cx] + cur[u] + Dist(cx,u);
ll d3 = cur[cy] + cur[u] + Dist(cy,u);
ll mx = max(d1,max(d2,d3));
if(mx == d3) cx = u;
else if(mx == d2) cy = u;
for(auto [v,w]:tr1[u]) if(v != fa && !vis[v]) updt(v,u);
}
void init(int u,int fa)
{
sz[u] = 1;
for(auto [v,w]:tr1[u]) if(v != fa && !vis[v])
{
cur[v] = cur[u] + w;
init(v,u);
sz[u] += sz[v];
}
}
void work(int u,int SZ)
{
getrt(u,0,SZ);
u = rt;
vis[u] = 1;
cur[u] = 0;
init(u,0);
cx = cy = u;
for(auto [v,w]:tr1[u]) if(!vis[v])
{
qry(v,u);
updt(v,u);
}
for(auto id:q[u])
{
ans[id] = max(ans[id],max(Dist(cx,B[id]) + cur[cx],Dist(cy,B[id]) + cur[cy]));
}
reverse(tr1[u].begin(),tr1[u].end());
cx = cy = u;
for(auto [v,w]:tr1[u]) if(!vis[v])
{
qry(v,u);
updt(v,u);
}
reverse(tr1[u].begin(),tr1[u].end());
for(auto [v,w]:tr1[u]) if(!vis[v]) work(v,sz[v]);
}
void solve()
{
cin>>n;
for(int i = 1;i <= n;i++) tr1[i].clear(),tr2[i].clear(),q[i].clear(),vis[i] = 0;
for(int i = 1,u,v,w;i < n;i++)
{
cin>>u>>v>>w;
tr1[u].pb(mkp(v,w));
tr1[v].pb(mkp(u,w));
}
for(int i = 1,u,v,w;i < n;i++)
{
cin>>u>>v>>w;
tr2[u].pb(mkp(v,w));
tr2[v].pb(mkp(u,w));
}
sum[0] = dfcnt = 0;
//O(1)求树上距离
dfs(1,0);
for(int i = 1;i <= 2*n-1;i++) st[0][i] = sum[rk[i]];
for(int i = 1;i < 18;i++)
for(int j = 1;j + (1<<i)<= 2*n;j++)
st[i][j] = min(st[i-1][j],st[i-1][j+(1<<i-1)]);
cin>>m;
for(int i = 1;i <= m;i++)
{
cin>>A[i]>>B[i];
ans[i] = 0;
q[A[i]].push_back(i);
}
work(1,n);
for(int i = 1;i <= m;i++) cout<<ans[i]<<"\n";
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
int T = 1;
while(T--) solve();
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 25896kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
21
result:
wrong answer 1st numbers differ - expected: '6', found: '21'